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 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$?

Input

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.

Output

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

Examples

Input 1

3 2 3
1 2 3
1 2
2 3

Output 1

1

Input 2

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

Output 2

0

Input 3

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

Output 3

0