Worst-case Expected Roads

You are given an undirected connected graph representing H country’s cities. There are N cities and E roads. It is guaranteed that between any two cities there is at most one road and the graph is connected. A random walk starts at city 1. At each step, if the current city is one of the K candidate cities \(\{c_1,c_2,\dots,c_K\}\) (i.e. the only possible locations of little \(w\)), the walk stops immediately. Otherwise, the walker moves to one of the adjacent cities chosen uniformly at random.

In the next several days, little \(c\) will try to find little \(w\) using this random strategy. He is interested in knowing, in the worst-case scenario (i.e. if little \(w\) happens to be at the candidate city that maximizes the expected number of roads traveled), what is the expected number of roads he has to go through. Output the answer as a reduced fraction \(\frac{P}{Q}\) (even if it is an integer, output in fraction form, for example, 4/1).

The equations used to compute the expected number \(T(v)\) from a non‐candidate vertex \(v\) are as follows:

[ T(v)=1+\sum_{u\in \mathrm{Adj}(v) \cap \overline{Q}}\frac{T(u)}{\deg(v)}\quad,\quad v\notin Q,\quad \text{and}\quad T(v)=0\text{ for }v\in Q. ]

Solve these linear equations (with \(v\) ranging over all non‐candidate vertices) to obtain \(T(1)\); this value is the expected number of roads traveled starting at city 1. If city 1 is in \(Q\), then \(T(1)=0\).

inputFormat

The first line of input contains three integers: N (number of cities), E (number of roads), and K (number of candidate cities).

Then follow E lines, each containing two integers u and v (1 ≤ u, v ≤ N) denoting an undirected road between cities u and v.

The last line contains K distinct integers representing the candidate cities \(c_1, c_2, \dots, c_K\).

It is guaranteed that the graph is connected and there is at most one road between any two distinct cities.

outputFormat

Output a single line containing the expected number of roads traveled (starting from city 1) in the worst-case candidate location, expressed as a reduced fraction in the format P/Q.

sample

3 2 1
1 2
2 3
1

0/1