시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 512 MB111100.000%

문제

Coloring of a labeled undirected graph with $n$ vertices in $k$ colors is an assignment of colors to its vertices, such that each vertex receives an integer color $x$ ($1 \leq x \leq k$) and no two adjacent vertices have the same color. A coloring can be treated as an array of integers from $1$ to $k$ of length $n$, $i$-th element of which corresponds to the color of the $i$-th vertex of the graph.

Coloring $b$ is monotonic to coloring $a$ of the same graph if \uline{exactly} one of the following statements holds:

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

Note that a coloring is not monotonic to itself because in that case both statements above hold.

You are given a labeled undirected graph and its coloring $a$ in $k$ colors. Is there a coloring $b$ of the given graph in $k$ colors which is monotonic to $a$?

입력

The first line contains three integers $n$, $m$ and $k$ ($1 \leq n, m, k \leq 3 \cdot 10^5$), the number of vertices in the graph, the number of the edges in the graph and the number of colors, respectively.

The second line contains $n$ integers $a_i$ ($1 \leq c_i \leq k$), the colors of vertices. 

$m$ lines follow. $i$-th of them contains two integers $u_i$ and $v_i$ ($1 \leq u_i < v_i \leq n$), describing an edge between vertices $u_i$ and $v_i$.

The graph doesn't contain loops or multiple edges. It is guaranteed that the array $a$ describes a valid coloring of the given graph.

출력

Print 1 if there exists a coloring $b$ monotonic to $a$ and print 0 otherwise.

예제 입력 1

3 2 3
1 2 3
1 2
2 3

예제 출력 1

1

예제 입력 2

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

예제 출력 2

0

예제 입력 3

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

예제 출력 3

0