Problem Description

There is a directed graph with $ N $ vertices and $ M $ edges. Each vertex $ i $ in this graph has an integer $ X_i $ written on it. A brother and sister who love games are about to play a game using this graph and a single chess piece.

• Initially, the piece is placed on vertex $ 1 $.
• On their turn, a player must perform exactly one of the following operations:
• Move: Move the piece exactly once to another vertex. If the piece is on vertex $ i $, it can only be moved to vertex $ j $ if there is a directed edge from vertex $ i $ to vertex $ j $.
• Declare End: End the game.
• The game alternates turns between the two players, and it ends when either player declares the end or immediately after the second player has made $ 10^9 $ moves. The integer written on the vertex where the piece is located at the end of the game is the score of the game.

The first player aims to maximize the score, while the second player aims to minimize it. What will be the score of the game?

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ X_1 $ $ X_2 $ ... $ X_N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ : $ A_M $ $ B_M $

• The first line contains the number of vertices $N\ (1\ ≦\ N\ ≦\ 100,000)$ and the number of edges $M\ (1\ ≦\ M\ ≦\ 200,000)$ separated by a space.
• The second line contains $ N $ integers separated by spaces, where the $i\ (1\ ≦\ i\ ≦\ N)$ -th integer $X_i\ (0\ ≦\ X_i\ ≦\ 10^9)$ represents the integer written on vertex $ i $.
• The next $ M $ lines contain edge information. The $i\ (1\ ≦\ i\ ≦\ M)$ -th line contains two integers $A_i, B_i\ (1\ ≦\ A_i\ ≦\ N,\ 1\ ≦\ B_i\ ≦\ N,\ A_i\ \neq\ B_i)$ separated by a space, indicating a directed edge from vertex $ A_i $ to vertex $ B_i $. It is guaranteed that no edge is given twice, i.e., if $p\ \neq\ q$, then $A_p\ \neq\ A_q$ or $B_p\ \neq\ B_q$.

Output Format

Output the score of the game in one line. End the output with a newline.

Sample Input and Output

Sample Input #1

3 3
1 3 2
1 2
2 3
3 1

Sample Output #1

2

Sample Input #2

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

Sample Output #2

1

Notes/Hints

Partial Points

This problem has partial points.

• If you solve the dataset where $N\ ≦\ 1000$ and $M\ ≦\ 2000$, you will be awarded $ 30 $ points.
• If you solve all test cases, you will be awarded an additional $ 70 $ points.

Sample Explanation 1

In this example, the game proceeds as follows:
- The first player moves the piece from vertex $ 1 $ to vertex $ 2 $.
- The second player moves the piece from vertex $ 2 $ to vertex $ 3 $.
- The first player declares the end of the game. The score is $ 2 $.

No matter what actions the first player takes, the second player can always take appropriate actions to prevent the score from being greater than $ 2 $. Similarly, no matter what actions the second player takes, the first player can always take appropriate actions to prevent the score from being less than $ 2 $.

Sample Explanation 2

In this example, the game proceeds as follows:
- The first player moves the piece from vertex $ 1 $ to vertex $ 2 $.
- The second player moves the piece from vertex $ 2 $ to vertex $ 4 $.
- The first player moves the piece from vertex $ 4 $ to vertex $ 3 $.
- The second player moves the piece from vertex $ 3 $ to vertex $ 1 $.
- The first player moves the piece from vertex $ 1 $ to vertex $ 2 $.
- The second player moves the piece from vertex $ 2 $ to vertex $ 4 $.
- (This sequence repeats for a while)
- The second player makes the $ 10^9 $ -th move, moving the piece from vertex $ 3 $ to vertex $ 1 $. The game ends, and the score is $ 1 $.

No matter what actions the first player takes, the second player can always take appropriate actions to prevent the score from being greater than $ 1 $. Similarly, no matter what actions the second player takes, the first player can always take appropriate actions to prevent the score from being less than $ 1 $.

见题面 Input 部分

见题面 Output 部分