题目描述

给定一个满足下列条件的图 $G$：

• $G$ 有 $N$ 个顶点和 $M$ 条边，顶点编号为 $1,2,\ldots,N$；
• 按以下方式绘制图形时，除圆周上的公共端点外，所有线段在圆内部互不相交：
  1. 画一个圆，在圆周上等间距放置 $N$ 个点，按顺序记为 $A_1,A_2,\ldots,A_N$；
  2. 若 $G$ 中顶点 $u$ 与 $v$ 之间有边，则连接 $A_u$ 与 $A_v$。

例如，下图在 $N=4,M=4$ 时满足条件：

而下图不满足条件，因为两条弦在圆内部相交：

对图 $G$ 进行染色，是指给每个顶点指定一种颜色，使每条边的两个端点颜色不同。

任意满足上述条件的图都可以使用至多四种颜色染色。四种颜色编号为 $1,2,3,4$。

现在给出 $K$ 个互不相同的颜色对 $(c_j,d_j)$。你还需要满足：对于每个给定颜色对，图中不能存在一条边，其两个端点的颜色分别为 $c_j$ 和 $d_j$。

请构造一种满足全部条件的染色；若不存在，则报告无解。

输入格式

第一行输入三个整数 $N,M,K$。

$$3\le N\le 200000, \qquad 1\le M\le 400000, \qquad 0\le K\le 6.$$

接下来 $M$ 行，每行输入两个整数 $u_i,v_i$，表示图中存在一条连接 $u_i$ 与 $v_i$ 的边。

$$1\le u_i<v_i\le N.$$

保证所有边互不相同。

接下来 $K$ 行，每行输入两个整数 $c_j,d_j$。

$$1\le c_j<d_j\le 4.$$

保证所有颜色对互不相同。

输出格式

若不存在满足条件的染色，输出一行 -1。

否则输出一行 $N$ 个整数，第 $i$ 个整数表示顶点 $i$ 的颜色。

样例 1

输入

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

输出

2 4 2 1

样例 2

输入

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

输出

-1