A graph $G$ is given that satisfies the following conditions:

• $G$ has $N$ vertices and $M$ edges, and the vertices are numbered from $1$ to $N$.
• The line segments drawn by the following process do not intersect inside the circle, excluding the circumference of the circle:
  1. Draw a circle and place $N$ points on it at equal intervals. Let these points be $A_{1}, \dots, A_{N}$ in order.
  2. If vertex $u$ and vertex $v$ are connected in $G$, connect point $A_{u}$ and point $A_{v}$ with a line segment.

For example, the following is a graph that satisfies the conditions when $N = 4$ and $M = 4$.

However, the following is not a graph that satisfies the conditions.

For a graph $G$, coloring $G$ means assigning a color to every vertex such that any two vertices connected by an edge have different colors.

Any graph satisfying the input conditions can always be colored using $4$ colors.

Let the $4$ distinct colors used for coloring be $1, 2, 3,$ and $4$.

Given $K$ distinct ordered pairs $(c_j, d_j)$ consisting of positive integers no greater than $4$, color $G$ such that there is no edge connecting a vertex of color $c_j$ and a vertex of color $d_j$.

Input

The first line contains the number of vertices $N$, the number of edges $M$, and the number of pairs $K$, separated by spaces. ($3 \le N \le 200\,000$; $1 \le M \le 400\,000$; $0 \le K \le 6$)

For $1 \le i \le M$, the $(i+1)$-th line contains information about the edge $u_i, v_i$, separated by a space. ($1 \le u_i < v_i \le N$; if $1 \le i_1 < i_2 \le M$, then $(u_{i_1}, v_{i_1}) \ne (u_{i_2}, v_{i_2})$) This means that vertex $u_i$ and vertex $v_i$ of graph $G$ are connected.

For $1 \le j \le K$, the $(M+j+1)$-th line contains $c_j$ and $d_j$. ($1 \le c_j < d_j \le 4$; if $1 \le j_1 < j_2 \le K$, then $(c_{j_1}, d_{j_1}) \ne (c_{j_2}, d_{j_2})$)

Output

If it is impossible to color the graph while satisfying the conditions, output only -1 on the first line.

If it is possible to color the graph while satisfying the conditions, output the colors of the $N$ vertices in order, separated by spaces, on the first line.

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