AT_abc366_g [ABC366G] XOR Neighbors

题目描述

问题陈述

给出一个具有 $N$ 个顶点和 $M$ 个边的简单无向图。第 $i$ 条边双向连接顶点 $u_i$ 和 $v_i$ 。

确定是否存在一种方法可以在此图的每个顶点上写入 $1$ 和 $2^{60} - 1$ 之间的整数，以满足以下条件:

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

输入格式

$N$ $M$
$u_1$ $v_1$
$u_2$ $v_2$
$\vdots$
$u_M$ $v_M$

输出格式

如果无法写入满足条件的整数，则输出 No。

否则，让 $X_v$ 成为写在顶点 $v$ 上的整数，并以下列格式输出解决方案：

Yes
$X_1$ $X_2$ $\dots$ $X_N$

如果存在多个解决方案，其中任何一个都将被接受。

输入输出样例 #1

输入 #1

3 3
1 2
1 3
2 3

输出 #1

Yes
4 4 4

输入输出样例 #2

输入 #2

2 1
1 2

输出 #2

No

输入输出样例 #3

输入 #3

1 0

输出 #3

Yes
1

输入输出样例 #4

输入 #4

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

输出 #4

Yes
12 4 4 8

说明/提示

• $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)$。
• 所有输入值都是整数。