You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

翻译自 CSES-1668 题。

题目描述

Uolevi 的班级中有 $n$ 名学生，学生之间有 $m$ 条友谊。你的任务是将学生分成两组，使得同一组内的学生之间没有友谊。你可以自由选择每组的大小。

输入格式

第一行包含两个整数 $n$ 和 $m$，分别表示学生的数量和友谊的数量。学生编号为 $1,2,…,n$。

接下来的 $m$ 行，每行包含两个整数 $a$ 和 $b$，表示学生 $a$ 和学生 $b$ 是朋友。

每条友谊连接的是两个不同的学生，且每两个学生之间至多有一条友谊。

输出格式

输出一种可能的分组方案。对于每个学生，输出 1 或 2，表示该学生被分配到第 $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$。