23676번 - Doesn't Contain Loops or Multiple Edges 다국어

문제

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.

제한

힌트