#P18763. [2025NA]Corporate Retreat

[2025NA]Corporate Retreat

题目描述

公司准备开展三项同时进行的团建活动。每名员工必须恰好参加其中一项。

公司已知某些员工两两关系密切。为促进新的交流,规定:任意一对关系密切的员工,不能参加同一项活动。

共有 NN 名员工,编号为 11 到 NN。其中前 KK 名为管理人员。特别地,题目保证:每一名非管理人员都至少与一名管理人员关系密切。

请判断能否满足上述要求。如果可以,还需要输出任意一种活动分配方案。

输入格式

第一行给出三个整数 N,K,MN,K,M,分别表示员工数、管理人员数和关系密切的员工对数。约束为:

1≤N≤1000,1\le N\le1000, 1≤K≤min⁡(7,N),1\le K\le\min(7,N), N−K≤M≤5000.N-K\le M\le5000.

接下来 MM 行,每行两个整数 i,ji,j,满足 1≤i<j≤N1\le i<j\le N,表示员工 ii 和 jj 关系密切。

同一对员工不会重复出现。每名编号大于 KK 的员工,都保证至少与一名编号不大于 KK 的员工有关系。

输出格式

若不存在合法方案,输出一行:

impossible

否则先输出:

possible

第二行输出 NN 个整数 a1,…,aNa_1,\ldots,a_N,其中 ai∈{1,2,3}a_i\in\{1,2,3\} 表示员工 ii 参加的活动。多个合法方案任选其一即可。

样例 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