27628번 - Treasure Hunter 다국어

Sckerin is a dungeon with N junctions (numbered from 1 to N) that are connected by M directed roads. A directed road (u, v) can be used to travel from junction u to junction v. To travel in its reverse direction (from v to u), you need to use the road (v, u) if there is one. There are no roads that start and end at the same junction. For each pair of junctions (u, v), there is at most one road from u to v.

There are T treasure chests scattered across Sckerin, and the i^th treasure chest is uniquely located at junction L_i. Collecting a treasure chest is easy as in a video game. You only need to visit the junction in which the treasure chest is located and the respective treasure chest is automatically collected.

Emma, a young treasure hunter, is set to collect all the treasure chests in Sckerin. She has a special device that allows her to teleport from any junction to another junction of her choice. However, using such a device too often might come with an unknown bad effect on her. Therefore, she would like to minimize the usage of such a device while being able to collect all the treasure chests.

Sckerin is protected by a guardian. Due to Emma’s charm, the guardian allows her to start her journey from any junction of her choice. From there, she might need to use the roads or her special device to collect all the treasure chests.

Help Emma to determine the minimum number of times she needs to use her special device to collect all the treasure chests.

The first line contains three integers N M T (2 ≤ N ≤ 500; 1 ≤ M ≤ N ˙ (N − 1); 1 ≤ T ≤ N) representing the number of junctions, the number of roads, and the number of treasure chests, respectively. The second line contains T integers L_i (1 ≤ L_i ≤ N) representing the junction in which the i^th treasure chest is located. It is guaranteed that there are no two treasure chests located at the same junction. The next M lines, each contains two integers u_i v_i (1 ≤ u_i, v_i ≤ N; u_i ≠ v_i) representing a directed road from junction u_i to junction v_i. It is guaranteed that the directed road (u_i, v_i) appears at most once.

Output in a line an integer representing the minimum number of times Emma needs to use her special device to collect all the treasure chests.