Cho một đồ thị $G$ thỏa mãn các điều kiện sau:

• $G$ có $N$ đỉnh và $M$ cạnh, các đỉnh được đánh số từ $1$ đến $N$.
• Các đoạn thẳng được vẽ theo quy trình sau đây không cắt nhau bên trong hình tròn (không tính phần chu vi):
  1. Vẽ một hình tròn và đánh dấu $N$ điểm cách đều nhau trên đường tròn. Gọi các điểm này theo thứ tự là $A_{1}, \cdots, A_{N}$.
  2. Nếu đỉnh $u$ và đỉnh $v$ được kết nối trong $G$, nối điểm $A_{u}$ và điểm $A_{v}$ bằng một đoạn thẳng.

Ví dụ, dưới đây là một đồ thị thỏa mãn các điều kiện khi $N = 4, M = 4$.

Tuy nhiên, đồ thị sau đây không thỏa mãn các điều kiện:

Đối với đồ thị $G$, việc tô màu $G$ có nghĩa là gán màu cho tất cả các đỉnh sao cho hai đỉnh được nối với nhau bởi một cạnh có màu khác nhau.

Bất kỳ đồ thị nào thỏa mãn các điều kiện đầu vào đều luôn có thể được tô màu bằng $4$ màu.

Giả sử $4$ màu khác nhau được sử dụng để tô màu là $1, 2, 3, 4$.

Cho $K$ cặp thứ tự khác nhau $(c_j, d_j)$ gồm các số nguyên dương không vượt quá $4$, hãy tô màu $G$ sao cho không tồn tại cạnh nào nối giữa một đỉnh có màu $c_j$ và một đỉnh có màu $d_j$.

Dữ liệu vào

Dòng đầu tiên chứa số đỉnh $N$, số cạnh $M$ và số cặp thứ tự $K$ của đồ thị $G$, cách nhau bởi dấu cách. ($3 \le N \le 200\,000$; $1 \le M \le 400\,000$; $0 \le K \le 6$)

Với $1 \le i \le M$, dòng thứ $(i+1)$ chứa thông tin về cạnh $u_i, v_i$ cách nhau bởi dấu cách. ($1 \le u_i < v_i \le N$; nếu $1 \le i_1 < i_2 \le M$ thì $(u_{i_1}, v_{i_1}) \ne (u_{i_1}, v_{i_2})$). Điều này có nghĩa là đỉnh $u_i$ và đỉnh $v_i$ của đồ thị $G$ được kết nối với nhau.

Với $1 \le j \le K$, dòng thứ $(M+j+1)$ chứa $c_j, d_j$. ($1 \le c_j < d_j \le 4$; nếu $1 \le j_1 < j_2 \le K$ thì $(c_{j_1}, d_{j_1}) \ne (c_{j_2}, d_{j_2})$).

Dữ liệu ra

Nếu không thể tô màu thỏa mãn các điều kiện, in ra -1 trên dòng đầu tiên.

Nếu có thể tô màu thỏa mãn các điều kiện, in ra màu của $N$ đỉnh theo thứ tự, cách nhau bởi dấu cách trên dòng đầu tiên.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

2 4 2 1

Dữ liệu vào 2

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

Dữ liệu ra 2

-1