XOR Neighbors

题目描述

你被给予一个包含 $N$) 个顶点和 $M$ 条边的简单无向图。第 $i$ 条边在顶点 $u_i$ 和 $v_i$ 之间双向连接。 判断是否存在一种方法，在图的每个顶点上写一个介于 $1$ 到 $2^{60} - 1$（含）之间的整数，使得满足以下条件：

对于每个度数至少为 $1$ 的顶点 $v$，其相邻顶点上所写数字的全部 XOR（不包含 $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$

3 3
1 2
1 3
2 3

Yes
4 4 4

2 1
1 2

No

1 0

Yes
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 < v_i \leq N $(u_i, v_i) \neq (u_j, v_j)$ 当 $i \neq j$。 所有输入值均为整数。其它可接受的解包括写成 $(2,2,2)$ 或 $(3,3,3)$。
可以写任意介于 $1$ 到 $2^{60} - 1$ 之间的整数。

标签: AtCoder|abc366G

来源

AtCoder|abc366G