迪玛来到了马地。这片土地上生活着n匹马。马地里的每匹马都有几个敌人(敌意是对称关系)。马地的敌意并不大,所以每匹马的敌人数量最多为3个。
现在马地正在进行竞选活动。因此,马匹相信迪玛会将它们分成两部分。马匹希望满足以下条件:一匹马的队伍中不应有超过一个敌人。
帮助迪玛将马匹分成几组。请注意,其中一方可能是空的。
输入
第一行包含两个整数 n, m $$( 1 \leq n \leq 3 \cdot 10^{5} ; 0 \leq m \leq \min ( 3 \cdot 10^{5}, \frac { n ( n - 1 ) } { 2 } ) )$$ — 马地中的马匹数量和敌人对的数量。
接下来的 m 行定义了敌人对。第 i 行包含整数 ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi),这意味着马 ai 是马 bi 的敌人。
考虑以某种方式从 1 到 n 索引的马。保证每匹马最多有三个敌人。输入中没有一对敌人出现超过一次。
输出
打印一行,由n个字符组成:如果马号i需要去第一方,则该行的第i个字符必须等于“0”,否则该字符应等于“1”。
如果无法按照要求划分马匹,则打印 -1。
示例
输入 #1
3 3 1 2 3 2 3 1
输出 #1
100
输入 #2
2 1 2 1
输出 #2
00
输入 #3
10 6 1 2 1 3 1 4 2 3 2 4 3 4
输出 #3
0110000000