4색 정리

아래 조건을 만족하는 그래프 $G$가 주어진다.

• $G$의 정점은 $N$개, 간선은 $M$개이며, 정점에는 $1$번부터 $N$번까지 정수 번호가 매겨져 있다.

• 다음 과정으로 그린 그림의 선분은 원의 둘레를 제외한 원의 내부에서 교차하지 않는다.

  1. 원을 그리고, 원 위에 일정한 간격으로 $N$개의 점을 찍는다. 이 점을 순서대로 $A_1$, $\cdots$, $A_N$이라 하자.
  2. $G$에서 $u$번 정점과 $v$번 정점이 연결되어 있다면, 점 $A_u$와 점 $A_v$를 선분으로 잇는다.

예를 들어, $N=4$, $M=4$일 때 조건을 만족하는 그래프는 다음과 같다.

반면, 다음은 조건을 만족하는 그래프가 아니다.

그래프 $G$를 색칠한다는 것은 간선으로 연결된 두 정점의 색이 서로 다르도록 모든 정점에 색을 부여하는 것이다.

입력 조건을 만족하는 그래프는 어떤 것이든 4개의 색으로 항상 색칠할 수 있다.

색칠에 쓰는 서로 다른 4개의 색을 각각 $1$, $2$, $3$, $4$라고 하자.

$4$ 이하의 양의 정수로 이루어진 서로 다른 $K$개의 순서쌍 $(c_j,d_j)$가 주어진다. 색이 $c_j$인 정점과 색이 $d_j$인 정점을 잇는 간선이 없도록 $G$를 색칠하여라.

첫 줄에 정점 수 $N$, 간선 수 $M$, 순서쌍 수 $K$가 공백을 사이에 두고 주어진다. ($3 \le N \le 200\,000$; $1 \le M \le 400\,000$; $0 \le K \le 6$)

$1 \le i \le M$에 대해, $(i+1)$번째 줄에는 간선 정보 $u_i$, $v_i$가 공백을 사이에 두고 주어진다. ($1 \le u_i < v_i \le N$; $1 \le i_1 < i_2 \le M$이면 $(u_{i_1},v_{i_1}) \ne (u_{i_2},v_{i_2})$) 이는 $G$의 $u_i$번 정점과 $v_i$번 정점이 연결되어 있다는 뜻이다.

$1 \le j \le K$에 대해, $(M+j+1)$번째 줄에는 $c_j$, $d_j$가 주어진다. ($1 \le c_j < d_j \le 4$; $1 \le j_1 < j_2 \le K$이면 $(c_{j_1},d_{j_1}) \ne (c_{j_2},d_{j_2})$)

조건을 만족하도록 색칠할 수 없다면 첫 줄에 -1만 출력한다.

조건을 만족하도록 색칠할 수 있다면 첫 줄에 $N$개 정점의 색을 1번 정점부터 차례로 공백을 사이에 두고 출력한다.