트래픽 엔지니어링

ISP(인터넷 서비스 제공자)는 매우 얇은 이윤으로 운영되기 때문에, 네트워크 트래픽을 보낼 최적 경로를 고르는 것은 회사의 생존에 중요합니다. 데이터를 보내는 사람을 위해, 인터넷상의 두 호스트 사이에서 가장 저렴한 경로를 찾으세요.

각 노드(호스트)는 다음과 같은 비용을 가집니다.

• 트래픽을 보내는 사람이 소유한 노드를 지나는 것은 사실상 공짜이므로 비용이 $0입니다.
• 다른 사람이 소유한 노드를 지나는 것은 노드당 $1의 비용이 듭니다.

경로의 비용은 그 경로가 지나는 모든 노드의 비용을 더한 값이며, 출발지 노드와 도착지 노드도 비용에 포함됩니다. 방향이 있는 간선을 따라 출발지에서 도착지까지 이동할 수 있는 경로들 중에서 비용이 최소가 되는 값을 구하세요.

입력은 여러 개의 네트워크로 이루어집니다. 각 네트워크는 다음 순서로 주어집니다.

1. 이어지는 네트워크 링크의 개수를 나타내는 정수 하나.
2. 그 개수만큼의 네트워크 링크. 각 링크는 두 이름의 쌍으로 주어지며, 첫 번째 이름에서 두 번째 이름으로 향하는 단방향(방향) 연결을 의미합니다.
3. 트래픽을 보내는 사람이 소유한 노드의 개수를 나타내는 정수 하나, 그리고 이어서 그 개수만큼의 소유 노드 이름.
4. 경로를 찾을 (출발지, 도착지) 쌍의 개수를 나타내는 정수 하나, 그리고 이어서 그 개수만큼의 노드 쌍. 각 쌍은 출발지가 먼저, 도착지가 나중에 주어집니다.

링크 개수가 0인 네트워크가 나오면 입력이 끝난 것이며, 그 네트워크는 처리하지 않습니다. 한 네트워크의 노드 수는 100개를 넘지 않습니다.

각 (출발지, 도착지) 쌍마다, 그 패킷을 보내는 데 드는 최소 비용을 나타내는 정수를 한 줄에 하나씩 출력합니다. 소유한 노드는 비용이 0이고, 소유하지 않은 노드는 비용이 1입니다. 출발지와 도착지 노드도 비용에 포함됩니다. 모든 네트워크의 모든 질의에 대해, 입력에 등장한 순서대로 결과를 출력합니다.