14742번 - Kimi No Ichi Wa.

여느 때와 같이 공허함을 느끼며 출근 전철을 타고 있던 타키와 미츠하는 창밖으로 서로를 보게 된다. 두 사람은 서로를 알아봤지만, 아쉽게도 전철 노선이 갈리면서 멀어지게 된다. 곧바로 서로를 찾아 나선 두 사람이 어디서 만날 수 있을까 궁금해진 당신은, 두 사람이 만날 수 있는 장소 중 전철 노선의 시작점에서 거리상으로 가장 가까운 곳을 찾아보려고 한다.

두 사람은 특별한 출근 티켓을 사용하기 때문에 이동할 수 있는 노선에 다음과 같은 특징이 있다.

• 각 역을 잇는 철도는 단방향이고, 같은 역을 잇는 철도(loop)는 존재하지 않는다.
• 시작점과 종점을 제외한 노선 위의 모든 역은 들어오는 철도의 수와 나가는 철도의 수가 같다.
• 시작점은 나가는 철도 하나, 종점은 들어오는 철도 하나에만 연결돼 있다.
• 임의의 역에서 출발해 그 역을 제외한 다른 역을 최대 한 번씩만 방문하고 돌아오는 경로는 최대 하나만 존재한다.
• 시작점에서 임의의 역으로 가는 경로가 항상 존재하고, 임의의 역에서 종점으로 가는 경로가 항상 존재한다.

만약 종점에 도달하면 무조건 전철에서 내려 회사로 출근해야 한다. 미츠하와 타키는 한시라도 빨리 만나고 싶어하기 때문에 쉬지 않고 계속해서 이동하고, 각 역 사이를 이동하는데 걸리는 시간은 모두 동일하다. 두 사람은 특별한 인연으로 이어져 있기 때문에 같은 역에 도착하면 무조건 서로를 만날 수 있다.

전철 노선의 정보와 현재 미츠하와 타키가 있는 역의 번호가 주어질 때, 두 사람이 만날 수 있는 역 중 노선의 시작점에서 가장 가까운 역의 번호를 출력하라. 만약 그러한 역이 없다면 "MUSUBI"를 출력하라.

첫 번째 줄에는 전철 역의 개수 N과 철도의 개수 M이 주어진다. N은 2이상 1,000,000 이하의 정수이다. 그 후 M개의 줄 각각에 두 정수 a, b(1<=a, b<=N)가 주어지는데 이는 a 역에서 b 역으로 가는 철도가 있다는 뜻이다. 마지막 줄에는 서로 다른 두 정수 s, t(1<=s, t<=N)가 주어지는데 각각 타키와 미츠하가 처음에 위치한 역의 번호이다. 항상 문제의 조건을 만족하는 입력만 주어진다.

첫 번째 줄에 두 사람이 만날 수 있는 역 중 노선의 시작점에서 가장 가까운 역의 번호를 출력하라. 만약 두 사람이 만날 수 없다면 “MUSUBI”를 출력하라.