← 返回题目列表

Codeforces · 272/E

E. 迪马和马

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

迪玛来到了马地。这片土地上生活着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