미스터리한 X 네트워크
면접 대비시간 제한1초메모리 제한128 MB
사람 N명의 무방향 그래프가 주어질 때, 두 사람 사이 최단 경로에 놓이는 중간 사람 수의 최솟값을 구한다.
문제
에콜 폴리테크니크(별명 “X”)는 카마라드(camarade) 네트워크로 유명하다. 카마라드란 같은 학교를 거쳐 간 동문을 뜻한다. 어떤 카마라드가 무언가(돈, 일자리 등)를 필요로 하면 이 네트워크에 도움을 청할 수 있다. 학번이 서로 다르더라도, 서로 아는 카마라드들을 중간에 거치면 원하는 상대에게 반드시 닿을 수 있다. 카마라드 관계는 대칭이며(서로 안다), 이 네트워크 덕분에 누구에게든 도달하는 경로가 항상 존재한다.
두 사람을 잇는 데 필요한 이러한 중간 카마라드의 수를 최소로 만드는 것이 목표다.
입력
첫째 줄에 카마라드의 수 ()이 주어진다. 카마라드에는 부터 까지 번호가 매겨져 있다.
이어지는 개의 줄은 각각 한 명의 카마라드를 설명한다. 각 줄은 그 카마라드의 번호 로 시작하고, 이어서 가 아는 카마라드의 수 (), 그리고 그 명의 번호가 온다. 한 줄의 모든 정수는 공백 하나로 구분된다.
마지막 줄에는 두 번호 과 ()가 주어진다. 은 도움을 청하는 카마라드, 는 도움을 받고 싶은 상대다.
출력
공백으로 구분된 세 정수 , , 그리고 에서 에 도달하는 데 필요한 중간 카마라드의 최소 수를 출력한다.
중간 카마라드란 최단 경로에서 과 를 제외하고 그 사이에 있는 사람들을 말한다. 두 사람이 서로 직접 알고 있다면 이 값은 이다.