eolymp
bolt
Try our new interface for solving problems
Problems

Horror List

Horror List

Time limit 1 second
Memory limit 128 MiB
prb6834-01

It was time for the 7th Nordic Cinema Popcorn Convention, and this year the manager Ian had a brilliant idea. In addition to the traditional film program, there would be a surprise room where a small group of people could stream a random movie from a large collection, while enjoying popcorn and martinis.

However, it turned out that some people were extremely disappointed, because they got to see movies like Ghosts of Mars, which instead caused them to tear out their hair in despair and horror.

To avoid this problem for the next convention, Ian has come up with a solution, but he needs your help to implement it. When the group enters the surprise room, they will type in a list of movies in a computer. This is the so-called horror list, which consists of bad movies that no one in the group would ever like to see. Of course, this list varies from group to group.

You also have access to the database Awesome Comparison of Movies which tells you which movies are directly similar to which. You can assume that movies that are similar to bad movies will be almost as bad. More specifically, we define the Horror index HI as follows:

HI = 0, if movie is on horror list. This overrides the other definitions.

HI = q + 1, if the worst directly similar movie has HI = q.

HI = +∞, if not similar at all to a horrible movie.

Input data

The first line contains three positive integers n, h, l (1h < n1000, 0l10000), where n is the number of movies (represented by IDs, ranging from 0 to n1), h is the number of movies on the horror list and l is the number of similarities in the database.

The second line contains h unique space-separated integers x[i] (0x[i] < n) denoting the ID of the movies on the horror list.

The following l lines contains two space-separated integers a[i], b[i] (0a[i] < b[i] < n), denoting that movie with IDa[i] is similar to movie with IDb[i] (and vice versa).

Output data

Output the ID of the best movie in the collection (highest Horror Index). In case of a tie, output the movie with the lowest ID.

Examples

Input example #1
6 3 5
0 5 2
0 1
1 2
4 5
3 5
0 2
Output example #1
1
Input example #2
6 2 3
5 2
0 5
0 1
3 4
Output example #2
3
Source 2012 Nordic Collegiate Programming Contest, October 6, Problem H