CSES1668 修建团队
#CS1668. 修建团队
修建团队
题目背景
翻译自 CSES-1668 题。
题目描述
Uolevi 的班级中有 n 名学生，学生之间有 m 条友谊。你的任务是将学生分成两组，使得同一组内的学生之间没有友谊。你可以自由选择每组的大小。
输入格式
第一行包含两个整数 n 和 m，分别表示学生的数量和友谊的数量。学生编号为 1,2,…,n1,2,…,n1,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
说明/提示