외판원

어떤 회사의 외판원들은 자신의 현재 위치를 회사에 주기적으로 보고한다. 또한 다른 위치로 이동할 때마다 새 위치를 보고해야 한다. 회사는 각 외판원의 이동 경로를 담당 구역 지도 위에 기록하고, 이 경로 정보를 외판원의 다음 업무 계획에 활용한다.

외판원의 담당 구역 지도는 연결된 무방향 그래프로 나타낸다. 정점은 외판원이 있을 수 있는 위치를, 간선은 위치 사이를 오가는 이동을 뜻한다. 따라서 외판원의 이동 경로는 그래프의 정점을 순서대로 나열한 수열로 표현된다.

외판원은 위치를 주기적으로 보고하고 한 곳에 오래 머무를 수도 있으므로, 같은 정점이 경로에 연달아 여러 번 나타날 수 있다. 경로에서 서로 이웃한 두 정점이 항상 같은 정점이거나 그래프에서 인접한 두 정점이면, 그 경로를 올바른 경로라고 부른다.

예를 들어 외판원의 담당 구역을 나타내는 아래 그래프에서

보고된 경로 [1 2 2 6 5 5 5 7 4]는 올바른 경로이다. 하지만 보고된 경로 [1 2 2 7 5 5 5 7 4]는 정점 $2$와 $7$ 사이에 간선이 없으므로 올바른 경로가 아니다. 외판원이 보고해야 할 때마다 (틀릴 수는 있어도) 매번 위치를 보고한다고 가정하면, 실제로 의도한 올바른 경로는 [1 2 2 4 5 5 5 7 4], [1 2 4 7 5 5 5 7 4], 또는 [1 2 2 6 5 5 5 7 4] 중 하나일 수 있다.

경로의 길이는 경로에 들어 있는 정점의 개수이다. 길이가 같은 두 경로 $A = a_1 a_2 \dots a_n$과 $B = b_1 b_2 \dots b_n$ 사이의 거리는 다음과 같이 정의한다.

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

여기서

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

이다.

외판원의 담당 구역 그래프와 (올바르지 않을 수도 있는) 이동 경로 $A$가 주어질 때, 길이가 같으면서 $\operatorname{dist}(A, B)$를 최소로 하는 올바른 경로 $B$를 찾아 그 최소 거리를 출력하는 프로그램을 작성하라.

입력의 첫 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 다음과 같은 형식이다.

각 테스트 케이스의 첫 줄에는 두 정수 $n_1$, $n_2$ ($3 \le n_1 \le 100$, $2 \le n_2 \le 4950$)가 주어진다. $n_1$은 그래프의 정점 수, $n_2$는 간선 수이며, 그래프는 연결 그래프이다. 정점은 $1$번부터 $n_1$번까지 번호가 매겨져 있다.

이어지는 $n_2$개의 줄에는 각각 간선 하나를 나타내는 두 정점이 주어진다.

테스트 케이스의 마지막 줄에는 이동 경로가 주어진다. 첫 정수 $n$ ($2 \le n \le 200$)은 경로의 길이이고, 그 뒤에 경로 위의 정점들을 순서대로 나타내는 $n$개의 정수가 주어진다.

각 테스트 케이스마다, 주어진 경로에서 길이가 같은 올바른 경로까지의 최소 거리를 한 줄에 출력한다.