좌회전
시간 제한8초메모리 제한512 MB
가로와 세로 도로로 이루어진 지도에서 우회전 없이 좌회전만으로 가는 최단 경로를 찾아 지나는 교차점 수를 세고, 경로가 없으면 impossible을 출력한다.
문제
타로는 대학 시절에 큰 노력 끝에 운전면허를 땄지만, 안타깝게도 운전할 기회가 전혀 없었다. 결국 그는 골드 면허를 받게 되었다.
어느 날, 그는 친구들과 당신을 포함해 교토로 여행을 가기로 계획했다. 회의 끝에 그들은 차로 돌아다니기로 합의했지만, 큰 문제가 있었다. 친구들 중 아무도 운전을 할 수 없었던 것이다. 그래서 그는 어쩔 수 없이 운전자가 되었다.
출발하는 날이 왔다. 그는 운전을 하겠지만, 반대 차선을 침범할까 봐 오른쪽으로는 절대 돌지 않을 것이다(일본에서는 차가 왼쪽으로 통행한다). 게다가 기술이 부족해 유턴도 할 수 없다. 차에는 내비게이션이 장착되어 있지만, 이 시스템은 우회전 없이 경로를 탐색하지 못한다. 그래서 그는 당신에게 부탁했다. “나는 우회전이 싫어. 그러니 이 내비게이션에서 가져온 도로 지도를 사용해, 목적지까지 좌회전만으로 가는 최단 경로를 찾는 프로그램을 작성해 줄 수 있겠어?”
입력
입력은 여러 데이터 세트로 구성된다. 입력의 첫 줄에는 데이터 세트의 수가 주어진다. 각 데이터 세트는 아래 형식으로 주어진다:
m n
name1 x1 y1
...
namem xm ym
p1 q1
...
pn qn
src dst
m은 교차로의 수이다. n은 도로의 수이다. namei는 i번째 교차로의 이름이다. (xi, yi)는 i번째 교차로의 정수 좌표이며, 양의 x는 동쪽, 양의 y는 북쪽을 향한다. pj와 qj는 j번째 도로의 끝점을 나타내는 교차로 이름이다. 모든 도로는 양방향이며 수직 또는 수평이다. src와 dst는 각각 출발 교차로와 목적지 교차로의 이름이다.
다음 사항을 가정할 수 있다:
- 2 ≤ m ≤ 1000, 0 ≤ xi ≤ 10000, 0 ≤ yi ≤ 10000;
- 각 교차로 이름은 길이가 최대 25인 하나 이상의 알파벳 문자로 이루어진 문자열이다;
- 같은 좌표를 공유하는 교차로는 없다;
- 끝점 외에 공통점을 가지는 도로 쌍은 없다;
- 중간에 교차로가 있는 도로는 없다;
- 두 교차로 사이에 도로가 두 개 이상 있는 경우는 없다;
- 타로는 어느 방향으로든 차를 출발시킬 수 있다; 그리고
- 출발 교차로와 목적지 교차로는 다르다.
입력 데이터에서 교차로가 세 개 미만의 도로와 연결된 경우가 있을 수 있다. 도로 지도에는 현지인이 아닌 사람에게 적합하지 않은 작은 도로가 포함되지 않았을 수 있다. 그런 경우에도 그곳을 통과할 때는 교차로로 간주해야 한다.
출력
각 데이터 세트에 대해, 타로가 우회전 없이 최단 거리의 경로로 운전할 때 적어도 몇 번 교차로를 통과해야 하는지 출력한다. 출발 교차로와 목적지 교차로는 타로가 출발하거나 도착할 때 “통과한” 것으로 간주해야 한다(따라서 세어야 한다). 또한 최단 경로가 여러 개 있을 수 있다.
우회전 없이 목적지에 도달하는 경로가 없으면 “impossible”을 출력한다.