A - Password Recovery Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

高橋君は、あるシステムのセキュリティ管理者です。このシステムでは、0 以上 10^9 以下の整数を要素とする長さ M の整数列がパスワードとして設定されています。

ある日、N 人のユーザーがそれぞれパスワードをメモした紙を提出しました。しかし、どのメモにもちょうど1箇所だけインクが滲んで読めなくなっている値があり、その箇所は -1 で表されています。それ以外の箇所はすべて正しく記録されています。

i 番目のユーザーのメモに書かれた整数列を S_{i,1}, S_{i,2}, \ldots, S_{i,M} とします。

高橋君は、すべてのメモが 同一のパスワード を記録したものであり得るかどうかを確認したいと考えています。すなわち、各メモの -1 の箇所を 0 以上 10^9 以下の適切な整数値で補うことで、すべてのメモが完全に一致するようにできるかを判定してください。

より正確には、以下の条件をすべて満たす、0 以上 10^9 以下の整数からなる長さ M の整数列 P = (P_1, P_2, \ldots, P_M) が存在するかどうかを判定してください。

  • 各メモ i（1 \leq i \leq N）について、S_{i,j} \neq -1 であるすべての位置 j（1 \leq j \leq M）において、S_{i,j} = P_j が成り立つ。

（S_{i,j} = -1 である位置については、P_j の値に関する制約はありません。）

条件を満たす P が存在するならば Yes を、存在しないならば No を出力してください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • N \times M \leq 2 \times 10^5
  • 各メモにはちょうど1箇所だけ -1 が含まれる。
  • S_{i,j} = -1 または 0 \leq S_{i,j} \leq 10^9（1 \leq i \leq N, 1 \leq j \leq M）
  • 入力はすべて整数である。

入力

N M
S_{1,1} S_{1,2} \cdots S_{1,M}
S_{2,1} S_{2,2} \cdots S_{2,M}
\vdots
S_{N,1} S_{N,2} \cdots S_{N,M}
  • 1 行目には、メモの枚数 N と、パスワードの長さ M が、スペース区切りで与えられる。
  • 続く N 行のうち i 行目（1 \leq i \leq N）には、i 番目のメモの整数列 S_{i,1}, S_{i,2}, \ldots, S_{i,M} がスペース区切りで与えられる。各メモにはちょうど1箇所だけ -1 が含まれ、それ以外の値は 0 以上 10^9 以下の整数である。

出力

条件を満たす整数列 P が存在するならば Yes を、存在しないならば No を1行で出力せよ。

入力例 1

3 4
-1 2 3 4
1 -1 3 4
1 2 -1 4

出力例 1

Yes

入力例 2

3 4
-1 2 3 4
1 -1 3 4
1 5 -1 4

出力例 2

No

入力例 3

5 6
-1 20 30 40 50 60
10 -1 30 40 50 60
10 20 -1 40 50 60
10 20 30 -1 50 60
10 20 30 40 -1 60

出力例 3

Yes

入力例 4

10 10
-1 2 3 4 5 6 7 8 9 10
1 -1 3 4 5 6 7 8 9 10
1 2 -1 4 5 6 7 8 9 10
1 2 3 -1 5 6 7 8 9 10
1 2 3 4 -1 6 7 8 9 10
1 2 3 4 5 -1 7 8 9 10
1 2 3 4 5 6 -1 8 9 10
1 2 3 4 5 6 7 -1 9 10
1 2 3 4 5 6 7 8 -1 10
1 2 3 4 5 6 7 8 9 -1

出力例 4

Yes

入力例 5

1 1
-1

出力例 5

Yes

Score : 266 pts

Problem Statement

Takahashi is the security administrator of a certain system. In this system, a password is set as an integer sequence of length M whose elements are integers between 0 and 10^9, inclusive.

One day, N users each submitted a piece of paper on which they had written down the password. However, on every memo, exactly one value has become unreadable due to ink smudging, and that position is represented by -1. All other positions are recorded correctly.

Let S_{i,1}, S_{i,2}, \ldots, S_{i,M} denote the integer sequence written on the i-th user's memo.

Takahashi wants to check whether it is possible that all memos recorded the same password. That is, determine whether it is possible to replace the -1 in each memo with an appropriate integer between 0 and 10^9, inclusive, so that all memos become completely identical.

More precisely, determine whether there exists an integer sequence P = (P_1, P_2, \ldots, P_M) of length M, consisting of integers between 0 and 10^9 inclusive, that satisfies all of the following conditions:

  • For each memo i (1 \leq i \leq N), for every position j (1 \leq j \leq M) where S_{i,j} \neq -1, it holds that S_{i,j} = P_j.

(For positions where S_{i,j} = -1, there are no constraints on the value of P_j.)

If such a P exists, print Yes; otherwise, print No.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • N \times M \leq 2 \times 10^5
  • Each memo contains exactly one -1.
  • S_{i,j} = -1 or 0 \leq S_{i,j} \leq 10^9 (1 \leq i \leq N, 1 \leq j \leq M)
  • All input values are integers.

Input

N M
S_{1,1} S_{1,2} \cdots S_{1,M}
S_{2,1} S_{2,2} \cdots S_{2,M}
\vdots
S_{N,1} S_{N,2} \cdots S_{N,M}
  • The first line contains the number of memos N and the password length M, separated by a space.
  • The following N lines each describe a memo. The i-th line (1 \leq i \leq N) contains the integer sequence S_{i,1}, S_{i,2}, \ldots, S_{i,M} separated by spaces. Each memo contains exactly one -1, and all other values are integers between 0 and 10^9, inclusive.

Output

Print Yes on a single line if an integer sequence P satisfying the conditions exists; otherwise, print No.

Sample Input 1

3 4
-1 2 3 4
1 -1 3 4
1 2 -1 4

Sample Output 1

Yes

Sample Input 2

3 4
-1 2 3 4
1 -1 3 4
1 5 -1 4

Sample Output 2

No

Sample Input 3

5 6
-1 20 30 40 50 60
10 -1 30 40 50 60
10 20 -1 40 50 60
10 20 30 -1 50 60
10 20 30 40 -1 60

Sample Output 3

Yes

Sample Input 4

10 10
-1 2 3 4 5 6 7 8 9 10
1 -1 3 4 5 6 7 8 9 10
1 2 -1 4 5 6 7 8 9 10
1 2 3 -1 5 6 7 8 9 10
1 2 3 4 -1 6 7 8 9 10
1 2 3 4 5 -1 7 8 9 10
1 2 3 4 5 6 -1 8 9 10
1 2 3 4 5 6 7 -1 9 10
1 2 3 4 5 6 7 8 -1 10
1 2 3 4 5 6 7 8 9 -1

Sample Output 4

Yes

Sample Input 5

1 1
-1

Sample Output 5

Yes