Дан граф $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$ раскраской называется такое назначение цветов всем вершинам, при котором любые две соединенные ребром вершины имеют разные цвета.

Любой граф, удовлетворяющий условиям ввода, всегда можно раскрасить в $4$ цвета.

Пусть $1, 2, 3, 4$ — четыре различных цвета, используемых для раскраски.

Даны $K$ различных пар $(c_j, d_j)$, состоящих из целых чисел от $1$ до $4$. Необходимо раскрасить граф $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_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