Một phép tô $k$ màu cho đồ thị vô hướng có nhãn gồm $n$ đỉnh là việc gán màu cho các đỉnh sao cho mỗi đỉnh nhận một màu nguyên $x$ ($1\leq x\leq k$) và không có hai đỉnh kề nhau nào cùng màu. Có thể coi một phép tô màu là một mảng độ dài $n$ gồm các số nguyên từ $1$ đến $k$, trong đó phần tử thứ $i$ tương ứng với màu của đỉnh thứ $i$ của đồ thị.

Phép tô màu $b$ đơn điệu đối với phép tô màu $a$ của cùng đồ thị nếu đúng chính xác một trong các mệnh đề sau:

1. $\forall_{1\leq i\leq n}\ a_i\leq b_i$
2. $\forall_{1\leq i\leq n}\ a_i\geq b_i$

Lưu ý rằng một phép tô màu không đơn điệu đối với chính nó vì khi đó cả hai mệnh đề trên đều đúng.

Cho một đồ thị vô hướng có nhãn và phép tô $k$ màu $a$ của nó. Có tồn tại phép tô $k$ màu $b$ của đồ thị đã cho đơn điệu đối với $a$ không?

Dữ liệu vào

Dòng đầu chứa ba số nguyên $n$, $m$ và $k$ ($1\leq n,m,k\leq 3\cdot 10^5$), lần lượt là số đỉnh, số cạnh và số màu.

Dòng thứ hai chứa $n$ số nguyên $a_i$ ($1\leq c_i\leq k$), là màu của các đỉnh.

Tiếp theo là $m$ dòng. Dòng thứ $i$ chứa hai số nguyên $u_i$ và $v_i$ ($1\leq u_i<v_i\leq n$), mô tả một cạnh giữa đỉnh $u_i$ và $v_i$.

Đồ thị không chứa khuyên hay cạnh bội. Bảo đảm mảng $a$ mô tả một phép tô màu hợp lệ của đồ thị đã cho.

Dữ liệu ra

In $1$ nếu tồn tại phép tô màu $b$ đơn điệu đối với $a$, ngược lại in $0$.

Ví dụ

Dữ liệu vào 1

3 2 3
1 2 3
1 2
2 3

Dữ liệu ra 1

1

Dữ liệu vào 2

3 3 3
1 2 3
1 2
2 3
1 3

Dữ liệu ra 2

0

Dữ liệu vào 3

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

Dữ liệu ra 3

0