GPS, 아이 러브 유

토마스 T. 가민(Thomas T. Garmin)은 작년 생일에 GPS를 선물받았고, 무척 마음에 들어 했다. 하지만 아쉽게도 토마스는 가끔 GPS가 안내하는 최단 경로 대신 경치 좋은 길로 돌아가고 싶을 때가 있었다. 설명서를 살펴보던 그는, 경로를 계산할 때 GPS가 반드시 지나가도록 특정 도로를 지정하면 기본 경로 탐색 알고리즘을 덮어쓸 수 있다는 것을 알게 되었다. 여러 번 시험해 본 결과, 원하는 경로를 얻는 데는 도로 하나만 강제해도 충분한 경우가 많았다. 그러나 더 구불구불한 경로에서는 더 많은 도로를 강제해야 했다. 결국 토마스는 매번 출발 전에 강제할 도로를 고르느라 시간을 너무 낭비하는 것은 아닌지 걱정하기 시작했다. 이제 그는 GPS의 즐거움을 누리는 대신, 운전 내내 다음과 같은 질문을 고민하며 괴로워한다. 더 적은 수의 도로만 강제해도 GPS가 이 경치 좋은 경로를 고르게 할 수 있었을까?

이 애틋한 사랑을 구해줄 수 있겠는가, 아니면 토마스와 그의 GPS는 서로 다른 길을 걸을 운명인가?

각 테스트 케이스는 여러 줄로 이루어진다. 첫 줄에는 도로의 끝점(교차점) 개수를 나타내는 정수 $n < 100$이 주어지며, 끝점은 $0$부터 $n-1$까지 번호가 매겨진다. 이어서 $n$개의 줄이 주어지고, 각 줄에는 $n$개의 음이 아닌 정수가 있다. $i$번째 줄의 $j$번째 값이 양수이면 끝점 $i$에서 끝점 $j$로 가는 도로의 길이를 뜻하고, $0$이면 두 끝점 사이에 도로가 없다는 뜻이다.

그 다음 줄에는 $m; p_1; p_2; p_3; \dots; p_m$ 형태로 토마스가 원하는 경치 좋은 경로가 주어진다. 이 경로는 $m-1$개의 도로로 이루어지며, 끝점 $p_1$에서 시작해 $p_2, p_3, \dots$를 그 순서대로 방문하여 끝점 $p_m$에서 끝난다. 마지막 테스트 케이스 다음에는 정수 $0$ 하나만 있는 줄이 온다.

토마스가 GPS에 강제할 도로를 지정할 때는 도로의 방향과 순서를 함께 지정한다는 점에 유의하라. 모든 경로는 단순 경로(같은 끝점을 두 번 지나지 않음)이며, 모든 도로의 길이는 $100$ 이하이다.

각 테스트 케이스마다 다음과 같이 한 줄을 출력한다.

Case n: k

여기서 $k$는 GPS가 지정된 경로를 고르도록 만들기 위해 토마스가 강제해야 하는 도로의 최소 개수이다. 최단 경로가 여러 개일 때 GPS는 그중 가장 경치 좋은 경로를 항상 선택한다고 가정한다. 따라서 주어진 강제 도로 집합을 사용하는 경로들 중에서 토마스의 경로가 최단 경로에 속한다면, GPS는 그 경로를 선택한다.