405094: GYM101790 D Scotland Yard's fail

Scotland Yard did not cope with the investigation of the series of murders, so Sherlock Holmes was called to the rescue.

After collecting the evidence on the crime scene, the great detective understood that all the murders were committed by one person, and all the dead were familiar with him.

Holmes knows all the pairs of people who were familiar with each other before the first murder was committed. He also knows that all the people who familiar with dead, including the murderer, come to his funeral and met there with each other (after that all these people will be familiar with each other). It is also known that the killer did not commit new murders until the end of the funeral of his previous victim.

Determine whether Sherlock Holmes has enough information to uniquely identify the killer, and the day after which a series of crimes could be stopped by arresting him.

The first line contains two integers N (2 ≤ N ≤ 10⁵) and M (1 ≤ M ≤ min(2 × 10⁵, N × (N - 1) / 2)), denoting the number of people and the number of familiarity relationships.

The next M lines contain two integers U_i and V_i (1 ≤ U_i, V_i ≤ N, U_i ≠ V_i), denoting person U_i and V_i were familiar before the first murder. Familiarity relationships are unique.

The next line contains one integer T (1 ≤ T ≤ N - 1), denoting the number of days.

The last line contains T number A_i, denoting a number of died person on i-th day.

Display two numbers: the number of the day after which you can uniquely identify the killer and his identifier. The days and IDs of people are numbered from 1.

If you can not identify the killer, display  - 1.

4 3
1 2
1 3
4 3
2
1 4

2 3

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

-1

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

4 3