회사 워크숍

회사는 직원들이 새로운 인맥을 쌓도록 돕기 위해 하루 일정의 워크숍을 떠난다. 워크숍에서는 세 가지 활동이 동시에 진행되므로 각 직원은 정확히 하나의 활동에 참여한다.

일부 직원 쌍은 이미 일상 업무에서 긴밀하게 협업한다. 직원들이 새로운 인맥을 쌓을 가능성을 최대화하기 위해, 이미 긴밀하게 협업하는 어떤 두 직원도 같은 활동에 배정되어서는 안 된다고 정한다. 또한 일부 직원은 임원이다. 회사 정책에 따라 임원이 아닌 모든 직원은 적어도 한 명의 임원과 긴밀하게 협업한다는 점에 유의한다.

해야 할 일은 긴밀하게 협업하는 어떤 두 직원도 같은 활동에 배정되지 않도록 각 직원을 활동에 배정할 수 있는지 판단하는 것이다.

입력의 첫 번째 줄에는 세 정수 $N$ ($1 \leq N \leq 1\,000$), $K$ $(1 \leq K \leq \min(7,N))$, 그리고 $M$ $(N-K \leq M \leq 5\,000)$가 주어진다. 여기서 $N$은 직원 수, $K$은 임원 수, $M$은 긴밀하게 협업하는 직원 쌍의 수이다. 직원에게는 $1$부터 $N$까지 번호가 매겨지며, 임원은 직원 $1$부터 $K$까지이다.

이어서 $M$개의 줄이 주어지며, 각 줄에는 두 정수 $i, j$가 주어진다. ($1 \leq i < j \leq N)$는 직원 $i$과 $j$이 서로 긴밀하게 협업한다는 의미이다. 긴밀하게 협업하는 직원 쌍은 두 번 이상 주어지지 않으며, 임원이 아닌 모든 직원은 적어도 한 명의 임원과 긴밀하게 협업한다.

첫 번째 줄에, 긴밀하게 협업하는 임의의 두 직원이 서로 다른 활동에 배정되도록 각 직원을 활동에 배정할 수 있는지를 나타내는 possible 또는 impossible를 출력한다.

가능하다면 두 번째 줄에 각각 $1$, $2$, 또는 $3$인 $N$개의 정수를 출력한다. 이 줄의 $i$번째 정수는 $i$번째 직원이 참여해야 하는 활동을 나타낸다. 올바른 해가 여러 개라면 그중 아무 것이나 출력해도 된다.