以下の条件を満たすグラフ $G$ が与えられる。

• $G$ は $N$ 個の頂点と $M$ 個の辺を持ち、頂点には $1$ から $N$ までの番号が付けられている。
• 次の手順で描かれる図において、線分は円の周を除いた円の内部で交差しない。
  1. 円を描き、その円周上に等間隔で $N$ 個の点を打つ。これらの点を順に $A_{1}, \dots, A_{N}$ とする。
  2. $G$ において頂点 $u$ と頂点 $v$ が接続されている場合、点 $A_{u}$ と点 $A_{v}$ を線分で結ぶ。

例えば、以下は $N = 4, M = 4$ のときに条件を満たすグラフである。

しかし、以下は条件を満たすグラフではない。

グラフ $G$ を彩色するとは、辺で結ばれた2つの頂点の色が異なるように、すべての頂点に色を割り当てることを意味する。

入力条件を満たす任意のグラフは、$4$ 色で彩色することが常に可能である。

彩色に使用する $4$ つの異なる色をそれぞれ $1, 2, 3, 4$ とする。

$4$ 以下の正の整数からなる異なる $K$ 個の順序対 $(c_j, d_j)$ が与えられるとき、色 $c_j$ の頂点と色 $d_j$ の頂点を結ぶ辺が存在しないように $G$ を彩色せよ。

入力

1行目に $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_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行目に -1 のみを出力する。

条件を満たすように彩色できる場合は、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