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