Numerical Graph

Input

The first line contains two integers $n$ and $m$ (1 \leq n \leq 250\,000, 1 \leq m \leq 500\,000)—representing the number of vertices and edges in the graph, respectively.

The second line contains $n$ integers a_i (1 \leq a_i \leq 10^9)—the numbers assigned to the vertices of the graph.

The following $m$ lines each contain two integers $x$ and $y$ (1 \leq x, y \leq n), indicating a directed edge from vertex $x$ to vertex $y$.

Output

Output a single integer on one line, which is the number the boys will obtain at the end of the game if both play optimally.

Examples

Note

In the first example, Figure 1 illustrates the graph from the first example. The vertices are labeled with their numbers and the game numbers in parentheses.

1. Vasyl makes the first move; he can either stop the game immediately or move to vertex $2$. The better choice is to move along the edge.

2. Next, Petryk moves, and it is advantageous for him to move to vertex $3$.

3. Finally, if Vasyl moves to vertex $1$, Petryk will end the game with the number $1$, so it's better to end the game immediately with the number $4$.

In the second example, Figure 2 shows the graph from the second example.

Here, the boys will alternately move for all 10^{100} steps until the token eventually stops at vertex $1$.

Scoring

1. ($6$ points) The given graph is a line with all edges directed in one direction.

2. ($8$ points) The given graph is a tree rooted at vertex $1$, with all edges directed away from the root.

3. ($14$ points) The given graph is a cycle.

4. ($26$ points) 1 \leq a_i \leq 2.

5. ($46$ points) Without additional constraints.