아래 조건을 만족하는 그래프 $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$에 대해, $G$를 색칠한다는 것은 간선으로 연결된 두 정점의 색이 다르도록 모든 정점에 색을 부여하는 것을 의미한다.

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

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

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

Input

첫 줄에 $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})$)

Output

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

조건을 만족하도록 색칠할 수 있다면 첫 줄에 $N$개의 정점의 색을 공백을 사이에 두고 순서대로 출력한다.

Examples

Input 1

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

Output 1

2 4 2 1

Input 2

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

Output 2

-1