Salesmen

Traveling salesmen of a company report their current location to the company on a regular basis. They must also report a new location whenever they move to a different place. The company records each salesman's working path on a map of his working area and uses that path to plan the salesman's next assignment.

The map of a salesman's working area is a connected, undirected graph. Vertices are the possible locations of the salesman and edges are the possible movements between locations. A salesman's working path is therefore a sequence of vertices in the graph.

Because a salesman reports his position regularly and may stay at one place for a very long time, the same vertex can appear several times in a row in a working path. A working path is called correct if, for every pair of consecutive vertices, the two vertices are either the same vertex or two adjacent vertices in the graph.

For example, on the graph below representing a salesman's working area,

the reported working path [1 2 2 6 5 5 5 7 4] is correct, but the reported working path [1 2 2 7 5 5 5 7 4] is not, because there is no edge between vertices $2$ and $7$. If we assume that the salesman reports his location every time he is required to (but possibly incorrectly), the intended correct path could be [1 2 2 4 5 5 5 7 4], [1 2 4 7 5 5 5 7 4], or [1 2 2 6 5 5 5 7 4].

The length of a working path is the number of vertices in it. For two paths $A = a_1 a_2 \dots a_n$ and $B = b_1 b_2 \dots b_n$ of the same length $n$, the distance between them is

$\operatorname{dist}(A, B) = \sum_{i=1}^{n} d(a_i, b_i)$

where

$d(a, b) = \begin{cases} 0 & (a = b) \\ 1 & (a \ne b) \end{cases}$

Given the graph of a salesman's working area and a working path $A$ (which may not be a correct path), compute a correct working path $B$ of the same length that minimizes $\operatorname{dist}(A, B)$, and report that minimum distance.

The first line contains the number of test cases $T$. Each test case has the following format.

The first line of a test case contains two integers $n_1$ and $n_2$ ($3 \le n_1 \le 100$, $2 \le n_2 \le 4950$), where $n_1$ is the number of vertices of the graph and $n_2$ is the number of edges. The graph is connected. Vertices are numbered from $1$ to $n_1$.

Each of the next $n_2$ lines contains two vertices describing one edge of the graph.

The last line of the test case describes a working path. The first integer $n$ ($2 \le n \le 200$) is the length of the path, followed by $n$ integers giving the sequence of vertices along the path.

For each test case, print a single line containing the minimum distance from the given path to a correct path of the same length.