CF272E Dima and Horses

Dima 来到了马之国。在这个国家里有 $n$ 匹马，每匹马都有一些敌人（敌对关系是相互的）。马之国整体并不很敌对，因此每匹马的敌人数量最多为 3 个。 现在，马之国正在进行选举活动。因此，马们信任 Dima，让他把它们分成两组。要求如下：每匹马在自己所在的组内，敌人数量不能多于 1 个。 请你帮助 Dima 将这些马分成两组。注意，其中一组可以是空的。

第一行包含两个整数 $n,m$，表示马之国中的马的数量和敌对对数。 接下来的 $m$ 行，每行表示一对敌对关系。第 $i$ 行包含整数 $a_{i},b_{i}$（$1\leq a_{i},b_{i}\leq n;\ a_{i}\ne b_{i}$），表示马 $a_{i}$ 和马 $b_{i}$ 是敌人。 假设马的编号为 $1$ 到 $n$。保证每匹马的敌人不超过 3 个。输入中不会有重复的敌对对。

输出一行，共 $n$ 个字符：如果第 $i$ 匹马应该被分到第一组，则第 $i$ 个字符为 “0”，否则为 “1”。 如果无法满足条件，将输出 $-1$。

由 ChatGPT 5 翻译