链接: https://cses.fi/problemset/task/1668

板块: Graph Algorithms

时限: 1.00 s ｜ 内存: 512 MB

题目描述

Uolevi 的班级里有 $n$ 名学生，以及他们之间的 $m$ 对友谊关系。你的任务是把学生分成两组，使得同一组中没有两个学生是朋友。你可以自由选择各组的人数。

输入

第一行输入包含两个整数 $n$ 和 $m$：学生数量和友谊关系数。学生编号为 $1,2,\dots,n$。

接着有 $m$ 行描述友谊关系。每行包含两个整数 $a$ 和 $b$：学生 $a$ 和 $b$ 是朋友。

每段友谊都发生在两名不同的学生之间。你可以假设任意两名学生之间至多有一段友谊。

输出

输出一种分组方案。对每名学生，根据它被分配到的组输出 "1" 或 "2"。你可以输出任意合法分组。

如果没有解，输出 "IMPOSSIBLE"。

数据范围

$1 \le n \le 10^5$ $1 \le m \le 2 \cdot 10^5$ $1 \le a,b \le n$

样例输入

5 3
1 2
1 3
4 5

样例输出

1 2 2 1 2