Optimal Road Reduction

You are given a bidirectional graph with N cities and M roads. In addition, K of these cities are designated as must‐include cities. Your goal is to remove as many roads as possible from the graph while keeping the subgraph induced by the must‐include cities connected.

More formally, you are given:

• An integer \(N\) representing the number of cities, labeled from 1 to \(N\).
• An integer \(M\) representing the number of bidirectional roads.
• A list of \(M\) roads, where each road connects two cities \(u\) and \(v\). This is represented as a pair \((u,v)\).
• An integer \(K\) and a list of \(K\) must‐include cities.

You are allowed to remove a road if, after its removal, the must–include cities (i.e. the cities in the given list) remain connected (there is a path between any two of them). Roads are processed in the given order. If removing a road disconnects the must–include cities, then that road must be kept in the final graph.

After processing all roads, consider the reduced graph that consists of the roads that were not removed. For each must–include city, compute the length of the longest shortest path from that city to any other city in the reduced graph. The answer is the maximum of these distances.

In mathematical terms, if \(d(u,v)\) is the shortest path length between cities \(u\) and \(v\) in the reduced graph, you need to output:

[ \max_{c \in C} ; \max_{v \in V} d(c, v), ]

where \(C\) is the set of must–include cities and \(V\) is the set of all cities. Note that all roads have unit length.

Note: You must read input from standard input and write the answer to standard output.

inputFormat

The input is given in the following format from standard input:

N M
u1 v1
u2 v2
... (M lines total)
K
c1 c2 ... cK

Here:

• N and M are the number of cities and roads respectively.
• Each of the next M lines contains two integers \(u\) and \(v\) representing a bidirectional road between cities \(u\) and \(v\).
• K is the number of must–include cities.
• The last line contains K integers representing the labels of the must–include cities.

outputFormat

Output a single integer to standard output – the length of the longest shortest path in the reduced graph after removing as many roads as possible while keeping all must–include cities connected.

## sample

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

2