你的公司将组织一次为期一天的员工迎新活动，以帮助员工建立新的联系。活动期间将同时进行三项不同的项目，因此每位员工都将恰好参加其中一项。

在日常工作中，有些员工之间已经存在密切的合作关系。为了最大化员工建立新联系的可能性，你规定任何两位已经密切合作的员工不能参加同一项活动。此外，公司中有一部分员工是高管（executives）。需要注意的是，根据公司政策，每位非高管员工都至少与一位高管密切合作。

你的任务是确定是否可能为每位员工分配一个活动，使得任何两位密切合作的员工都被分配到不同的活动中。

输入格式

输入的第一行包含三个整数：$N$（$1 \le N \le 1\,000$）、$K$（$1 \le K \le \min(7, N)$）和 $M$（$N - K \le M \le 5\,000$）。其中，$N$ 是员工人数，$K$ 是高管人数，$M$ 是密切合作的员工对数。员工的编号为 $1$ 到 $N$，其中高管是编号为 $1$ 到 $K$ 的员工。

接下来的 $M$ 行，每行包含两个整数 $i, j$（$1 \le i < j \le N$），表示员工 $i$ 和员工 $j$ 之间存在密切合作关系。任何一对密切合作的员工不会被重复列出，且每位非高管员工都至少与一位高管密切合作。

输出格式

第一行输出 possible 或 impossible，表示是否可能为每位员工分配活动，并确保任何两位密切合作的员工都被分配到不同的活动中。

如果可能，在第二行输出 $N$ 个整数，每个整数为 $1$、$2$ 或 $3$。这一行中的第 $i$ 个整数表示第 $i$ 位员工应该参加的活动。如果存在多个可行解，你可以输出其中任意一个。

样例

输入样例 1

5 2 7
1 2
1 3
2 3
2 4
2 5
3 4
4 5

输出样例 1

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

输出样例 2

impossible

输入样例 3

3 2 2
1 3
2 3

输出样例 3

possible
1 1 2