Dany jest graf $G$ spełniający poniższe warunki:

• Graf $G$ posiada $N$ wierzchołków i $M$ krawędzi, a wierzchołki są ponumerowane liczbami całkowitymi od $1$ do $N$.
• Odcinki narysowane zgodnie z poniższym procesem nie przecinają się wewnątrz koła (z wyłączeniem jego obwodu):
  1. Rysujemy koło i zaznaczamy na nim $N$ punktów w równych odstępach. Oznaczmy te punkty w kolejności jako $A_{1}, \dots, A_{N}$.
  2. Jeśli wierzchołek $u$ jest połączony z wierzchołkiem $v$ w grafie $G$, łączymy punkty $A_{u}$ oraz $A_{v}$ odcinkiem.

Na przykład, poniżej znajduje się graf spełniający te warunki dla $N = 4$ oraz $M = 4$.

Z kolei poniższy graf nie spełnia tych warunków.

Dla grafu $G$, pokolorowanie grafu oznacza przypisanie koloru każdemu wierzchołkowi w taki sposób, aby żadne dwa połączone krawędzią wierzchołki nie miały tego samego koloru.

Każdy graf spełniający warunki wejściowe można zawsze pokolorować przy użyciu $4$ kolorów.

Niech $1, 2, 3, 4$ będą czterema różnymi kolorami używanymi do pokolorowania.

Mając dane $K$ różnych par $(c_j, d_j)$ składających się z dodatnich liczb całkowitych nieprzekraczających $4$, należy pokolorować graf $G$ tak, aby nie istniała żadna krawędź łącząca wierzchołek o kolorze $c_j$ z wierzchołkiem o kolorze $d_j$.

Wejście

W pierwszej linii podano liczbę wierzchołków $G$ oznaczaną jako $N$, liczbę krawędzi $M$ oraz liczbę par $K$, oddzielone spacjami ($3 \le N \le 200\,000$; $1 \le M \le 400\,000$; $0 \le K \le 6$).

Dla $1 \le i \le M$, w $(i+1)$-szej linii podano informacje o krawędziach $u_i, v_i$ oddzielone spacjami ($1 \le u_i < v_i \le N$; jeśli $1 \le i_1 < i_2 \le M$, to $(u_{i_1}, v_{i_1}) \ne (u_{i_1}, v_{i_2})$). Oznacza to, że wierzchołek $u_i$ jest połączony z wierzchołkiem $v_i$ w grafie $G$.

Dla $1 \le j \le K$, w $(M+j+1)$-szej linii podano $c_j, d_j$ ($1 \le c_j < d_j \le 4$; jeśli $1 \le j_1 < j_2 \le K$, to $(c_{j_1}, d_{j_1}) \ne (c_{j_2}, d_{j_2})$).

Wyjście

Jeśli pokolorowanie spełniające warunki nie jest możliwe, w pierwszej linii należy wypisać -1.

Jeśli pokolorowanie spełniające warunki jest możliwe, w pierwszej linii należy wypisać kolory $N$ wierzchołków w kolejności, oddzielone spacjami.

Przykład

Wejście 1

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

Wyjście 1

2 4 2 1

Wejście 2

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

Wyjście 2

-1