← 返回题目列表

Codeforces · 1211/I

I. 不寻常的图表

中文机器翻译题面 查看原题

Ivan 在生日那天收到了非负整数数组 $$$a_1, a_2, \ldots, a_n$$$。他立即注意到所有 $$$a_i$$$ 都满足条件 $$$0 \leq a_i \leq 15$$$。

Ivan非常喜欢图论,所以他决定将他的序列转化为图。

他的图中将会有 $$$n$$$ 个顶点,并且当且仅当整数 $$$a_u$$$ 和 $$$a_v$$$ 的二进制表示法恰好有一位不同时,顶点 $$$u$$$ 和 $$$v$$$ 才会出现在图中(换句话说,对于某个整数,$$$a_u \oplus a_v = 2^k$$$ $$$k \geq 0$$$。其中$$$\oplus$$$ 是按位异或)。

几天后发生了一件可怕的事情,Ivan 忘记了他的序列 $$$a$$$,他只记得构造图!

你能帮助他,找到任意序列 $$$a_1, a_2, \ldots, a_n$$$,使得按照 Ivan 使用的相同规则构建的图将与他的图相同吗?

输入

输入的第一行包含两个整数 $$$n,m$$$ ($$$1 \leq n \leq 500, 0 \leq m \leq \frac{n(n-1)}{2}$$$):Ivan 图中的顶点和边的数量。

接下来的 $$$m$$$ 行包含边的描述:第 $$$i$$$ 行包含两个整数 $$$u_i, v_i$$$ ($$$1 \leq u_i, v_i \leq n; u_i \neq v_i$$$),描述连接顶点 $$$u_i$$$ 和 $$$v_i$$$ 的无向边图表。

保证图中不存在重边。保证给定的图存在某种解。

输出

输出 $$$n$$$ 空格分隔的整数,$$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_i \leq 15$$$)。

打印的数字应满足约束:当且仅当对于某个整数 $$$k \geq 0$$$,$$$a_u \oplus a_v = 2^k$$$ 时,图中存在顶点 $$$u$$$ 和 $$$v$$$ 之间的边。

保证给定的图存在某种解。如果有多个可能的解决方案,则可以输出任何一个。

示例

输入 #1

4 4
1 2
2 3
3 4
4 1

输出 #1

0 1 0 1

输入 #2

3 0

输出 #2

0 0 0