Se proporciona un grafo $G$ que satisface las siguientes condiciones:

• $G$ tiene $N$ vértices y $M$ aristas, y los vértices están numerados con enteros del $1$ al $N$.
• Los segmentos de línea dibujados mediante el siguiente proceso no se cruzan dentro del círculo, excluyendo su circunferencia:
  1. Se dibuja un círculo y se marcan $N$ puntos a intervalos regulares sobre él. Llamemos a estos puntos $A_{1}, \dots, A_{N}$ en orden.
  2. Si el vértice $u$ y el vértice $v$ están conectados en $G$, se traza un segmento de línea entre el punto $A_{u}$ y el punto $A_{v}$.

Por ejemplo, el siguiente es un grafo que satisface las condiciones cuando $N = 4$ y $M = 4$.

Sin embargo, el siguiente no es un grafo que satisfaga las condiciones.

Para un grafo $G$, colorear $G$ significa asignar un color a cada vértice de modo que dos vértices conectados por una arista tengan colores diferentes.

Cualquier grafo que satisfaga las condiciones de entrada siempre se puede colorear con $4$ colores.

Llamemos a los $4$ colores distintos utilizados para colorear como $1, 2, 3, 4$.

Dados $K$ pares ordenados distintos $(c_j, d_j)$ formados por enteros positivos menores o iguales a $4$, colorea $G$ de tal manera que no exista ninguna arista que conecte un vértice de color $c_j$ con un vértice de color $d_j$.

Entrada

La primera línea contiene el número de vértices $N$, el número de aristas $M$ y el número de pares ordenados $K$, separados por espacios. ($3 \le N \le 200\,000$; $1 \le M \le 400\,000$; $0 \le K \le 6$)

Para $1 \le i \le M$, la línea $(i+1)$ contiene la información de la arista $u_i, v_i$ separada por un espacio. ($1 \le u_i < v_i \le N$; si $1 \le i_1 < i_2 \le M$, entonces $(u_{i_1}, v_{i_1}) \ne (u_{i_1}, v_{i_2})$). Esto significa que el vértice $u_i$ y el vértice $v_i$ del grafo $G$ están conectados.

Para $1 \le j \le K$, la línea $(M+j+1)$ contiene $c_j, d_j$. ($1 \le c_j < d_j \le 4$; si $1 \le j_1 < j_2 \le K$, entonces $(c_{j_1}, d_{j_1}) \ne (c_{j_2}, d_{j_2})$).

Salida

Si no es posible colorear el grafo cumpliendo las condiciones, imprime únicamente -1 en la primera línea.

Si es posible colorear el grafo cumpliendo las condiciones, imprime en la primera línea los colores de los $N$ vértices en orden, separados por espacios.

Ejemplos

Entrada 1

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

Salida 1

2 4 2 1

Entrada 2

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

Salida 2

-1