도로 뒤집기
면접 대비시간 제한8초메모리 제한512 MB
방향 그래프에서 간선을 최대 하나 뒤집을 수 있을 때 S에서 T까지 최단 거리와 뒤집을 간선 번호를 구하고, 도움이 되는 간선이 없으면 0을 출력한다.
문제
Andrew R. Klein은 Yanwoe라는 도시에 살면서 평일마다 이 도시에 있는 직장으로 출근한다. 그는 이 도시의 도로 교통에 완전히 질려 버렸다. 이 도시의 모든 도로는 일방통행이라, 그는 자신이 생각하는 것보다 더 먼 길을 돌아가야 한다.
어느 날 Andrew는 이런 생각을 떠올렸다. "도로 하나의 표지판을 반대 방향으로 바꾸면 어떨까? 표지판 하나만 바꾸면 내 행동이 드러나지 않을 거야. 물론 출근 경로를 가능한 한 짧게 만들고 싶어. 어느 도로의 방향을 바꿔야 하지?" 정말 영리한 사람이다.
Andrew는 최대 도로 하나의 방향을 바꿀 수 있을 때 최단 경로를 찾는 프로그램을 작성해 달라고 요청했다. 공범에 대한 처벌은 걱정하지 않아도 된다. 당신은 Andrew와 다른 나라에 살고 있어서 그의 나라 법으로 처벌받을 수 없기 때문이다. 그러니 그를 도와주자.
입력
입력은 여러 데이터셋으로 이루어지며, 각 데이터셋의 형식은 다음과 같다.
N
S T
M
A1 B1
A2 B2
...
AM BM
N은 지점의 수이다. S와 T는 각각 Andrew의 집과 직장이 있는 지점을 나타낸다. M은 도로의 수이다. Ai와 Bi는 각각 i번째 도로의 시작점과 끝점을 나타낸다. 각 지점은 1부터 N까지의 고유한 번호로 식별된다. 어떤 도로는 시작점과 끝점이 같은 지점일 수 있다. 또한 같은 시작점과 끝점을 잇는 도로가 여러 개 있을 수 있다.
다음 조건이 모두 성립한다고 가정할 수 있다. 1 ≤ N ≤ 1000, 1 ≤ M ≤ 10000, S ≠ T.
입력은 0 하나만 포함하는 줄로 끝난다. 이 줄은 어떤 데이터셋에도 속하지 않으므로 처리하지 않는다.
출력
각 데이터셋마다 최단 거리(지나는 도로의 수로 센다)와 방향을 바꿔야 하는 도로 번호를 한 줄에 출력한다. 최단 거리를 얻는 방법이 여러 가지라면 도로 번호가 가장 작은 방법을 고른다. 방향을 바꿔서 더 짧은 경로가 만들어지지 않으면 도로 번호로 0을 출력한다.
거리와 도로 번호는 공백 하나로 구분한다. 다른 문자는 출력하지 않는다.