异或邻居

题目描述

给定一个具有 $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$ 的顺序无关。

输入格式

输入按以下格式从标准输入给出：

$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$

样例

3 3
1 2
1 3
2 3

Yes
4 4 4

其他可接受的方案包括写入 $(2,2,2)$ 或 $(3,3,3)$。

2 1
1 2

No

1 0

Yes
1

可以写入介于 $1$ 到 $2^{60} - 1$ 之间的任意整数。

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

Yes
12 4 4 8

数据范围

• $1 \leq N \leq 60$
• $0 \leq M \leq N(N-1)/2$
• $1 \leq u_i \lt v_i \leq N$
• 对于 $i \neq j$，有 $(u_i, v_i) \neq (u_j, v_j)$。
• 所有输入值均为整数。

提示

答案不唯一，输出任意合法解即可。