103666: [Atcoder]ABC366 G - XOR Neighbors
Description
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$.
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
Output
得分：600分
问题陈述
给定一个简单无向图，有N个顶点和M条边。第i条边双向连接顶点u_i和v_i。
判断是否存在一种方式，在每个顶点上写一个介于1到2^60 - 1（包括）之间的整数，使得以下条件得到满足：
- 对于每个度数至少为1的顶点v，其相邻顶点上写的数字的总异或和为0（不包括v本身）。
什么是异或？
两个非负整数A和B的异或，记作A ⊕ B，定义如下：- 在A ⊕ B的二进制表示中，位置2^k（k ≥ 0）的位是1，当且仅当在A和B的二进制表示中位置2^k的位中恰好有一个是1。否则，它是0。
一般来说，k个整数p_1, …, p_k的按位异或定义为((…((p_1 ⊕ p_2) ⊕ p_3) ⊕ …) ⊕ p_k)。可以证明这与p_1, …, p_k的顺序无关。
约束条件
- 1 ≤ N ≤ 60
- 0 ≤ M ≤ N(N-1)/2
- 1 ≤ u_i < v_i ≤ N
- 对于i ≠ j，有(u_i, v_i) ≠ (u_j, v_j)。
- 所有输入值都是整数。
输入
输入从标准输入以下格式给出：
N M u_1 v_1 u_2 v_2 … u_M v_M
输出
如果没有办法写出满足条件的整数，打印"No"。
否则，设X_v为顶点v上写的整数，并以以下格式打印你的解决方案。如果存在多个解决方案，任何一个都会被接受。
Yes X_1 X_2 … 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 - 1之间的整数。
样本输入4
4 5 1 2 1 3 2 3 2 4 3 4
样本输出4
Yes 12 4 4 8