給定一個滿足以下條件的圖 $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$，著色是指為所有頂點分配顏色，使得任何由邊相連的兩個頂點顏色不同。

滿足輸入條件的任意圖皆保證可以使用 $4$ 種顏色進行著色。

設用於著色的 $4$ 種不同顏色分別為 $1, 2, 3, 4$。

給定 $K$ 個由 $4$ 以下的正整數組成的相異數對 $(c_j, d_j)$，請對 $G$ 進行著色，使得不存在任何邊連接顏色為 $c_j$ 的頂點與顏色為 $d_j$ 的頂點。

輸入格式

第一行包含 $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})$)

輸出格式

若無法滿足條件進行著色，則第一行僅輸出 -1。

若可以滿足條件進行著色，則第一行依序輸出 $N$ 個頂點的顏色，以空格分隔。

範例

輸入格式 1

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

輸出格式 1

2 4 2 1

輸入格式 2

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

輸出格式 2

-1