Numerical Graph
Vasyl and Petryk have discovered a numerical graph—a connected directed graph where each vertex has a number assigned to it.
The boys are in need of a number, so they decided to play a game on this graph. They start by placing a token on vertex number 1. In each move, they can either end the game and take the number from the vertex where the token is currently located or move the token to an adjacent vertex via a directed edge. After moves, the game concludes automatically, and they take the number from the vertex where the token is positioned.
Vasyl plays first, trying to maximize the number, while Petryk aims to minimize it. Determine the number they will obtain at the end of the game if both players make optimal moves.
Input
The first line contains two integers and ()—representing the number of vertices and edges in the graph, respectively.
The second line contains integers ()—the numbers assigned to the vertices of the graph.
The following lines each contain two integers and (), indicating a directed edge from vertex to vertex .
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.
Vasyl makes the first move; he can either stop the game immediately or move to vertex . The better choice is to move along the edge.
Next, Petryk moves, and it is advantageous for him to move to vertex .
Finally, if Vasyl moves to vertex , Petryk will end the game with the number , so it's better to end the game immediately with the number .
In the second example, Figure 2 shows the graph from the second example.
Here, the boys will alternately move for all steps until the token eventually stops at vertex .
Scoring
( points) The given graph is a line with all edges directed in one direction.
( points) The given graph is a tree rooted at vertex 1, with all edges directed away from the root.
( points) The given graph is a cycle.
( points) .
( points) Without additional constraints.