← 返回题目列表

AtCoder · tupc2024_h

H. 12 格

中文机器翻译题面 查看原题

配点 : 100 点

問題文

N \times N 网格。从上面 i 行,从左起 j 标记列中的方块 表示为 (i,j) 。

另外, M 整数 4 津 (t_k,i_k,j_k,d_k)\; (k=1,2,\dots,M) 。(t,i,j,d) 满足以下条件:

  • t 是 0 或 1
  • t=0 如果 1 \leq i\leq N-1, 1 \leq j \leq N
  • t=1 如果 1 \leq i \leq N, 1 \leq j \leq N-1
  • d 是 1 或 2

判断是否存在一种在网格的每个方格中写入整数的方法满足以下所有条件,如果有,则配置一种。

  • 每个方格中写入的整数是 是小于或等于 0 以上 10^9 的整数
  • 上、下、左、右相邻方格中写入的整数之差的绝对值为 1 或 2 是 对于
  • 各 k=1,2,\dots,M ,以下情况成立
    • t_k=0 如果是这样,质量 (i_k,j_k),(i_k+1,j_k) 中写入的整数之间的差的绝对值为 d_k 是 对于
    • t_k=1 如果是这样,质量 (i_k,j_k),(i_k,j_k+1) 中写入的整数之间的差的绝对值为 d_k 是 对于

制約

  • 1 \leq N \leq 1000
  • 0 \leq M \leq \min\{2 \times 10^5,2N(N-1)\}
  • (t_k,i_k,j_k,d_k) 满足问题陈述的条件
  • k \neq \ell 如果 (t_k,i_k,j_k) \neq (t_\ell,i_\ell,j_\ell)
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N M
t_1 i_1 j_1 d_1
t_2 i_2 j_2 d_2
\vdots
t_M i_M j_M d_M

出力

如果没有满足条件的写法 No 。

如果存在, 输出N+1 行。 对于第1 行是 一个整数,表示第 Yes 。 在i+1 \; (i=1,2\dots,N) 行中, 按此顺序输出要写入 (i,1),(i,2),\dots,(i,N) 的整数,并用空格分隔。

如果有多个解,则可以输出任意一个。


入力例 1

2 3
0 1 1 2
1 1 1 1
0 1 2 2

出力例 1

Yes
0 1
2 3

此外,

Yes
5 4
3 2

也是正确的。


入力例 2

2 3
0 1 1 2
1 1 1 2
1 2 1 1

出力例 2

Yes
0 2
2 3

此外,

Yes
0 2
2 1

也是正确的。


入力例 3

2 4
0 1 1 2
1 1 1 2
1 2 1 1
0 1 2 2

出力例 3

No

没有满足条件的写入方法。 求