Building Teams

题目描述

Uolevi 的班上有 $n$ 名学生，和 $m$ 条友谊关系。你需要把学生分成两队，使得任意一队中没有两个学生是朋友。你可以自由选择两队的大小。

输入格式

第一行包含两个整数 $n$ 和 $m$：学生数量和友谊数量。学生编号为 $1,2,\dots,n$。 接下来有 $m$ 行描述友谊。每行有两个整数 $a$ 和 $b$：学生 $a$ 和 $b$ 是朋友。 每条友谊发生在两个不同的学生之间。你可以假设任意两名学生之间最多只有一条友谊。

输出格式

输出一个构造队伍的示例。对于每个学生，输出 "1" 或 "2" 表示该学生被分配到哪一队。你可以输出任何一个合法的分配。 如果不存在解，输出 "IMPOSSIBLE"。

5 3
1 2
1 3
4 5

1 2 2 1 2

提示

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

标签: CSES1668|图论

来源

CSES1668|图论