예약 오류

사장이 화가 났다. 비서가 예약한 미국행 항공권이 잘못됐기 때문이다. 사장은 경유를 가장 적게 하는 일정을 원했는데, 비서가 예약해 둔 구간은 그 조건을 만족하지 않는다. 이미 결제한 구간은 그대로 두기로 했으니, 프로그래머인 당신이 최소한의 구간만 새로 예약해서 항공권을 고쳐야 한다.

공항 두 곳을 잇는 직항 노선이 모두 주어진다. 각 노선은 양쪽 방향으로 이용할 수 있다. 비서가 이미 예약한 구간도 항공권에 적힌 순서대로 주어진다. 여행은 항공권의 첫 공항에서 시작해 마지막 공항에서 끝난다.

직항 노선으로 갈 수 있는 가장 적은 구간 수로 출발 공항에서 목적지까지 갈 수 있게 하려면 구간을 최소 몇 개 더 예약해야 하는지 구하시오.

이미 예약한 구간은 시간이 자유로워서 어떤 순서로도 이용할 수 있다. 사장은 새로 예약한 구간과 함께 이미 예약한 구간을 전부 이용해도 되고, 일부만 이용해도 되고, 하나도 이용하지 않아도 된다. A에서 B로 예약한 구간은 A에서 B로만 이용할 수 있고, B에서 A로는 이용할 수 없다.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 100$) 각 테스트 케이스는 $N + 2$개 줄로 이루어진다.

각 테스트 케이스의 첫 줄에 직항 노선의 개수 $N$이 주어진다. ($1 \le N \le 100\,000$) 이어지는 $N$개 줄에는 직항 노선으로 이어진 서로 다른 공항 두 곳의 이름이 주어지며, 이 노선은 양쪽 방향으로 이용할 수 있다. 공항 이름은 대문자 세 글자다. 한 테스트 케이스 안에서 같은 공항 쌍을 잇는 노선은 많아야 한 개다.

각 테스트 케이스의 마지막 줄에 잘못 예약된 항공권이 $M$ $A_1$ $A_2$ $\ldots$ $A_{M+1}$ 형태로 주어진다. $M$은 이미 예약한 구간의 개수이고, $A_i$는 공항 이름이다. 연달아 적힌 두 공항은 앞 공항에서 뒤 공항으로 예약한 구간 하나를 뜻한다. 예약이 워낙 엉망이라 같은 공항을 여러 번 지나거나 같은 구간을 두 번 이상 예약한 경우도 있다. 다만 예약된 구간은 모두 위에 주어진 $N$개 노선 중 하나다. 사장은 $A_1$에서 출발해 $A_{M+1}$까지 간다.

각 테스트 케이스마다, 이미 예약한 구간과 합쳐서 $A_1$에서 $A_{M+1}$까지 가장 적은 구간 수로 갈 수 있게 만드는 데 필요한 추가 예약 구간의 최소 개수를 한 줄에 하나씩 출력한다.

예제의 첫 번째 테스트 케이스에서는 FRA에서 JFK로 가는 구간이나 CAI에서 LHR로 가는 구간을 예약하면 CAI에서 JFK까지 한 번만 경유해서 갈 수 있고, 이것이 가능한 최소 경유 횟수다.

두 번째 테스트 케이스에서 최소 경유 횟수는 CAI, FRA, LHR, JFK 경로로만 달성할 수 있다. 비서는 LHR에서 FRA로 가는 구간을 예약했고 그 반대 방향은 예약하지 않았으므로, FRA에서 LHR로 가는 구간을 새로 예약해야 한다.

세 번째 테스트 케이스에서는 비서가 최적의 항공권을 예약했으므로 더 예약할 구간이 없다.