Problem D
Horror List

Photo by Janet Hudson
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 specificly, we define the Horror index as follows:

\[ HI = \left\{ \begin{array}{ll} 0 & \textrm{if movie is on horror list. This overrides the other definitions.} \\ Q+1 & \textrm{if the worst directly similar movie has $HI = Q$} \\ +\infty & \textrm{if not similar at all to a horrible movie} \end{array} \right. \]


The first line of input contains three positive integers $N$, $H$, $L$ ($1 \leq H < N \leq 1\, 000,0 \leq L \leq 10\, 000$), where $N$ is the number of movies (represented by IDs, ranging from $0$ to $N-1$), $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$ ($0 \leq x_ 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$ ($0 \leq a_ i < b_ i < N$), denoting that movie with ID $a_ i$ is similar to movie with ID $b_ i$ (and vice versa).


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

Sample Input 1 Sample Output 1
6 3 5
0 5 2
0 1
1 2
4 5
3 5
0 2
Sample Input 2 Sample Output 2
6 2 3
5 2
0 5
0 1
3 4

Please log in to submit a solution to this problem

Log in