Score : $600$ points

问题陈述

给定一个简单的无向图，包含 $N$ 个顶点和 $M$ 条边。第 $i$ 条边双向连接顶点 $u_i$ 和 $v_i$。

确定是否存在一种方法，为这个图的每个顶点写上一个介于 $1$ 和 $2^{60} - 1$（包括两端）之间的整数，以满足以下条件：

• 对于每个度数至少为 $1$ 的顶点 $v$，其相邻顶点（不包括 $v$ 本身）上写的数字的总异或值为 $0$。

什么是异或？两个非负整数 $A$ 和 $B$ 的异或，记作 $A \oplus B$，定义如下：

• 在 $A \oplus B$ 的二进制表示中，位置 $2^k \, (k \geq 0)$ 的位是 $1$ 当且仅当在 $A$ 和 $B$ 的二进制表示中位置 $2^k$ 的位中恰好有一个是 $1$。否则，它是 $0$。

例如，$3 \oplus 5 = 6$（二进制：$011 \oplus 101 = 110$）。 一般来说，$k$ 个整数 $p_1, \dots, p_k$ 的按位异或定义为 $(\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k)$。可以证明，这与 $p_1, \dots, p_k$ 的顺序无关。

以上为大语言模型 kimi 翻译，仅供参考。

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