New Online Judge 主页 问题 来源/分类 竞赛&作业 状态 排名 常见问答
登录 注册

2182: 团建分组

内存限制：512 MB 时间限制：2 S 标准输入输出
题目类型：传统 评测方式：Special Judge 上传者：
提交：3 通过：2
提交提交记录统计

题目描述

软件公司有若干个办公室，每个办公室都有一个HR。
CEO和所有HR互相认识，HR和本办公室的员工互相认识。
此外，可能还有其他人互相认识，包括：CEO和其他员工、同办公室员工、跨办公室员工、HR和其他办公室员工等等。
现在已知公司总共有 N 人（包含CEO和HR），总共存在M条互相认识的关系。
你不知道CEO、HR是谁，CEO最多认识15个员工（包含HR），并且最多存在8个办公室。
请判断能否将N人分成三组，要求每组中的人两两不认识彼此。
注意：上述互相认识为对称关系，如果A认识B，但B不认识A，这种关系不满足互相认识，可以看作两两不认识彼此。

输入格式

第一行为正整数N和M，2≤N≤1000,1≤M≤100000。
接下来M行，每行两个整数u和v，表示员工u和员工v互相认识，1≤u≠v≤N。
输入保证满足题目约束：CEO至多认识15个员工；至多存在8个办公室；CEO与HR互相认识，HR与本办公室员工互相认识。

输出格式

如果存在划分方式，按顺序输出每个员工的组号：1、2、3。
如果有多解，输出任意一解即可。
如果无解，输出Impossible。

输入样例 复制 

样例1：
4 3
1 2
1 3
3 4

样例2：
4 6
1 2
1 3
1 4
2 3
2 4
3 4

输出样例 复制 

样例1：
1 2 2 3

样例2：
Impossible

数据范围与提示

来源：2023 NCPC