G - XOR Neighbors Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 600 点

問題文

N 頂点 M 辺の単純無向グラフが与えられます。i 番目の辺は頂点 u_i と v_i を双方向に結びます。

このグラフの各頂点に 1 以上 2^{60} 未満の整数を書き込む方法であって、次の条件を満たすものが存在するか判定し、存在するならば一つ構築してください。

  • 次数が 1 以上のすべての頂点 v について、隣接する頂点 (v 自身は含まない) に書き込まれている数の総 XOR が 0 となる
XOR とは 非負整数 A,B の XOR A \oplus B は、以下のように定義されます。
  • A \oplus B を二進表記した際の 2^k \, (k \geq 0) の位の数は、A,B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
例えば、 3 \oplus 5 = 6 となります (二進表記すると: 011 \oplus 101=110)。
一般に k 個の整数 p_1, \dots, p_k の XOR は (\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k) と定義され、これは p_1, \dots, p_k の順番によらないことが証明できます。

制約

  • 1 \leq N \leq 60
  • 0 \leq M \leq N(N-1)/2
  • 1 \leq u_i < v_i \leq N
  • i \neq j ならば (u_i,v_i) \neq (u_j,v_j)
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

出力

条件を満たす整数の書き込み方が存在しないならば、Noを出力せよ。

存在するならば、頂点 v に書き込む整数を X_v として、以下の形式で出力せよ。答えが複数ある場合、どれを出力しても良い。

Yes
X_1 X_2 \dots X_N

入力例 1

3 3
1 2
1 3
2 3

出力例 1

Yes
4 4 4

他にも、(2,2,2) や (3,3,3) を書き込んでも正解になります。

入力例 2

2 1
1 2

出力例 2

No

入力例 3

1 0

出力例 3

Yes
1

1 以上 2^{60} 未満のどの整数を書き込んでも正解になります。

入力例 4

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

出力例 4

Yes
12 4 4 8

Score : 600 points

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The i-th edge connects vertices u_i and v_i bidirectionally.

Determine if there exists a way to write an integer between 1 and 2^{60} - 1, inclusive, on each vertex of this graph so that the following condition is satisfied:

  • For every vertex v with a degree of at least 1, the total XOR of the numbers written on its adjacent vertices (excluding v itself) is 0.
What is XOR? The XOR of two non-negative integers A and B, denoted as A \oplus B, is defined as follows:
  • In the binary representation of A \oplus B, the bit at position 2^k \, (k \geq 0) is 1 if and only if exactly one of the bits at position 2^k in the binary representations of A and B is 1. Otherwise, it is 0.
For example, 3 \oplus 5 = 6 (in binary: 011 \oplus 101 = 110).
In general, the bitwise XOR of k integers p_1, \dots, p_k is defined as (\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k). It can be proved that this is independent of the order of p_1, \dots, p_k.

Constraints

  • 1 \leq N \leq 60
  • 0 \leq M \leq N(N-1)/2
  • 1 \leq u_i < v_i \leq N
  • (u_i, v_i) \neq (u_j, v_j) for i \neq j.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

Output

If there is no way to write integers satisfying the condition, print No.

Otherwise, let X_v be the integer written on vertex v, and print your solution in the following format. If multiple solutions exist, any of them will be accepted.

Yes
X_1 X_2 \dots X_N

Sample Input 1

3 3
1 2
1 3
2 3

Sample Output 1

Yes
4 4 4

Other acceptable solutions include writing (2,2,2) or (3,3,3).

Sample Input 2

2 1
1 2

Sample Output 2

No

Sample Input 3

1 0

Sample Output 3

Yes
1

Any integer between 1 and 2^{60} - 1 can be written.

Sample Input 4

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

Sample Output 4

Yes
12 4 4 8