32116번 - 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$일 때 조건을 만족하는 그래프이다.

N = 4, M = 4일 때 조건을 만족하는 그래프

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

조건을 만족하는 그래프가 아님

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

입력 조건을 만족하는 임의의 그래프는 4ドル$개의 색으로 색칠하는 것이 항상 가능하다.

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

4ドル$ 이하의 양의 정수로 이루어진 서로 다른 $K$개의 순서쌍 $(c_j,d_j)$가 주어질 때, 색이 $c_j$인 정점과 $d_j$인 정점을 연결하는 간선이 존재하지 않도록 $G$를 색칠하여라.

입력

첫 줄에 $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_1},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$개의 정점의 색을 공백을 사이에 두고 순서대로 출력한다.

제한

힌트