#P18763. [2025NA]Corporate Retreat
[2025NA]Corporate Retreat
题目描述
公司准备开展三项同时进行的团建活动。每名员工必须恰好参加其中一项。
公司已知某些员工两两关系密切。为促进新的交流,规定:任意一对关系密切的员工,不能参加同一项活动。
共有 名员工,编号为 到 。其中前 名为管理人员。特别地,题目保证:每一名非管理人员都至少与一名管理人员关系密切。
请判断能否满足上述要求。如果可以,还需要输出任意一种活动分配方案。
输入格式
第一行给出三个整数 ,分别表示员工数、管理人员数和关系密切的员工对数。约束为:
接下来 行,每行两个整数 ,满足 ,表示员工 和 关系密切。
同一对员工不会重复出现。每名编号大于 的员工,都保证至少与一名编号不大于 的员工有关系。
输出格式
若不存在合法方案,输出一行:
impossible
否则先输出:
possible
第二行输出 个整数 ,其中 表示员工 参加的活动。多个合法方案任选其一即可。
样例 1
输入
5 2 7
1 2
1 3
2 3
2 4
2 5
3 4
4 5
输出
possible
2 1 3 2 3
样例 2
输入
5 2 8
1 2
1 3
2 3
2 4
2 5
3 4
3 5
4 5
输出
impossible
样例 3
输入
3 2 2
1 3
2 3
输出
possible
1 1 2