On donne un graphe $G$ satisfaisant les conditions suivantes :

• $G$ possède $N$ sommets et $M$ arêtes, et les sommets sont numérotés de $1$ à $N$.
• Les segments de droite tracés selon le procédé suivant ne se croisent pas à l'intérieur du cercle (à l'exclusion de la circonférence) :
  1. On trace un cercle et on place $N$ points à intervalles réguliers sur celui-ci. Appelons ces points $A_{1}, \dots, A_{N}$ dans l'ordre.
  2. Si le sommet $u$ et le sommet $v$ sont reliés dans $G$, on relie le point $A_{u}$ et le point $A_{v}$ par un segment de droite.

Par exemple, voici un graphe satisfaisant ces conditions pour $N = 4$ et $M = 4$.

Cependant, le graphe suivant ne satisfait pas ces conditions.

Pour un graphe $G$, colorier $G$ signifie attribuer une couleur à chaque sommet de telle sorte que deux sommets reliés par une arête aient des couleurs différentes.

Tout graphe satisfaisant les conditions d'entrée peut toujours être colorié avec $4$ couleurs.

Soient $1, 2, 3, 4$ les quatre couleurs distinctes utilisées pour le coloriage.

Étant donné $K$ paires ordonnées distinctes $(c_j, d_j)$ composées d'entiers positifs inférieurs ou égaux à $4$, coloriez $G$ de telle sorte qu'aucune arête ne relie un sommet de couleur $c_j$ à un sommet de couleur $d_j$.

Entrée

La première ligne contient le nombre de sommets $N$, le nombre d'arêtes $M$ et le nombre de paires $K$, séparés par des espaces. ($3 \le N \le 200\,000$ ; $1 \le M \le 400\,000$ ; $0 \le K \le 6$)

Pour $1 \le i \le M$, la $(i+1)$-ième ligne contient les informations sur l'arête $u_i, v_i$ séparées par un espace. ($1 \le u_i < v_i \le N$ ; si $1 \le i_1 < i_2 \le M$, alors $(u_{i_1}, v_{i_1}) \ne (u_{i_2}, v_{i_2})$). Cela signifie que le sommet $u_i$ et le sommet $v_i$ du graphe $G$ sont reliés.

Pour $1 \le j \le K$, la $(M+j+1)$-ième ligne contient $c_j$ et $d_j$. ($1 \le c_j < d_j \le 4$ ; si $1 \le j_1 < j_2 \le K$, alors $(c_{j_1}, d_{j_1}) \ne (c_{j_2}, d_{j_2})$).

Sortie

Si le coloriage satisfaisant les conditions est impossible, affichez uniquement -1 sur la première ligne.

Si le coloriage satisfaisant les conditions est possible, affichez sur la première ligne les couleurs des $N$ sommets, séparées par des espaces et dans l'ordre.

Exemples

Entrée 1

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

Sortie 1

2 4 2 1

Entrée 2

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

Sortie 2

-1