Problem D
Corporate Retreat

Your company is going on a one-day retreat to help your employees build new connections. Three activities will be run simultaneously at the retreat so each employee will participate in exactly one activity.

Some pairs of employees already work closely in their day-to-day operations. To maximize the likelihood of employees making new connections, you declare that no two employees that already work closely should be in the same activity. Finally, some of your employees are executives. Note, due to company policy every employee that is not an executive works closely with at least one executive.

Your job is to determine if it is possible to assign each employee to an activity so that no two employees that work closely are assigned to the same activity.

Input

The first line of input contains three integers: $N$ ($1 \leq N \leq 1\, 000$), $K$ $(1 \leq K \leq \min (7,N))$, and $M$ $(N-K \leq M \leq 5\, 000)$. Here, $N$ is the number of employees, $K$ is the number of executives, and $M$ is the number of pairs of employees that work closely. The employees are numbered from $1$ to $N$, and the executives are employees $1$ through $K$.

Then $M$ lines follow, each containing two integers $i, j$ ($1 \leq i < j \leq N)$ meaning employees $i$ and $j$ work closely together. No pair of employees that work closely will be listed more than once and every employee that is not an executive will work closely with at least one executive.

Output

In the first line, output possible or impossible, indicating whether or not it is possible to assign each employee to an activity while ensuring any two employees that work closely are assigned to different activities.

If it is possible, output a second line containing $N$ integers, each being $1$, $2$, or $3$. The $i$-th integer on this line indicates the activity that the $i$-th employee should attend. If there are multiple valid solutions, you may output any.

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

possible
2 1 3 2 3

5 2 8
1 2
1 3
2 3
2 4
2 5
3 4
3 5
4 5

impossible

3 2 2
1 3
2 3

possible
1 1 2