CF272E.Dima and Horses

Dima came to the horse land. There are n horses living in the land. Each horse in the horse land has several enemies (enmity is a symmetric relationship). The horse land isn't very hostile, so the number of enemies of each horse is at most 3.

Right now the horse land is going through an election campaign. So the horses trusted Dima to split them into two parts. At that the horses want the following condition to hold: a horse shouldn't have more than one enemy in its party.

Help Dima split the horses into parties. Note that one of the parties can turn out to be empty.

迪马来到了马国。马国生活着 $n$ 匹马。马国中的每匹马都有若干个敌人（敌对关系是对称的）。马国并不十分好斗，因此每匹马的敌人数量至多为 3。

目前马国正处在选举活动期间，于是马们委托迪马将它们分成两组。同时，马们希望满足如下条件：一匹马在其所在组中至多只能有一个敌人。

请帮助迪马将马们分组。注意：其中一组可以为空。

The first line contains two integers n, m — the number of horses in the horse land and the number of enemy pairs.

Next m lines define the enemy pairs. The i-th line contains integers a__i, b__i (1 ≤ a__i, b__i ≤ n; a__i ≠ b__i), which mean that horse a__i is the enemy of horse b__i.

Consider the horses indexed in some way from 1 to n. It is guaranteed that each horse has at most three enemies. No pair of enemies occurs more than once in the input.

第一行包含两个整数 $n$ 和 $m$ —— 分别表示马国中马的数量以及敌对关系对的数量。

接下来的 $m$ 行定义了敌对关系对。第 $i$ 行包含两个整数 $a_i$、$b_i$（满足 $1 \leq a_i, b_i \leq n$；$a_i \neq b_i$），表示马 $a_i$ 与马 $b_i$ 互为敌人。

假设这些马被以某种方式从 $1$ 到 $n$ 编号。题目保证每匹马至多有三个敌人。输入中不会重复出现同一对敌对关系。

Print a line, consisting of n characters: the i-th character of the line must equal "0", if the horse number i needs to go to the first party, otherwise this character should equal "1".

If there isn't a way to divide the horses as required, print -1.

输出一行，包含 n 个字符：该行的第 i 个字符应为 "0"，当且仅当编号为 i 的马需要去第一个聚会；否则该字符应为 "1"。

如果不存在满足要求的分组方式，则输出 -1。