404771: GYM101628 H Have Some Cheese Bread

Coming back from Foz, Gabi and Divino were headed to the boarding gate. Gabi, hungry, realized the large quantity of Cheese Bread Houses in the way and wondered which way they should take so they can pass by the maximum number of Cheese Bread Houses. Divino, however, wasn't that hungry, and wanted to know which way would minimize the number of Cheese Bread Houses.

Additionally, the airport has a strange property. The walkways between each terminal are unidirectional and, if there is a path leaving from Terminal A to Terminal B, there is no path from Terminal B to Terminal A.

Initially they are at Terminal 1 and the Gate is at Terminal N.

The first line of input contains 3 integers, N, C and M (1 ≤ N ≤ 10⁵, 1 ≤ C ≤ N, 1 ≤ M ≤ 10⁵), indicating, respectively, the number of terminals (identifies from 1 to N), Cheese Bread Houses and walkways. The second line contains C integers, the indices of the terminals that have a Cheese Bread House. Finally, the following M lines contain 2 integers v and w, indicating thar there is a walkway from v to w.

The output must contain a single line with 2 space separated integers Min and Max, the minimum and maximum number of Cheese Bread Houses by which they may pass by when going from Terminal 1 to Terminal N.

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

1 3