103666: [Atcoder]ABC366 G - XOR Neighbors

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

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

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。
例如,3 ⊕ 5 = 6(二进制:011 ⊕ 101 = 110)。
一般来说,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

加入题单

上一题 下一题 算法标签: