给定一个满足以下条件的图 $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$ 的顶点相连的边。

输入格式

第一行包含三个整数 $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_2}, 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