우유 공장
면접 대비시간 제한2초메모리 제한512 MB
방향 트리에서 모든 다른 정점에서 도달할 수 있는 가장 작은 정점을 찾고, 그런 정점이 없으면 -1을 출력한다.
문제
우유 사업이 잘 되고 있다! 농부 존의 우유 가공 공장은 개의 가공 스테이션으로 이루어져 있고, 스테이션에는 의 번호가 붙어 있다 (). 또한 개의 통로가 있으며, 각 통로는 두 스테이션을 연결한다. 통로를 만드는 데는 돈이 많이 들기 때문에, 존은 어떤 스테이션에서 출발해도 다른 모든 스테이션에 도달할 수 있도록 최소 개수의 통로만 설치했다.
효율을 높이기 위해 존은 모든 통로에 컨베이어 벨트를 설치했다. 그런데 각 컨베이어 벨트가 한 방향으로만 움직인다는 사실을 너무 늦게 깨달았다. 이제 통로를 따라 이동하는 것은 한 방향으로만 가능하다! 따라서 더 이상 어떤 스테이션에서든 다른 어떤 스테이션으로든 갈 수 있는 것은 아니다.
그래도 존은 모든 다른 스테이션에서 스테이션 로 결국 이동할 수 있는 스테이션 가 적어도 하나 존재한다면 모든 것이 끝난 것은 아니라고 생각한다. 다른 임의의 스테이션 에서 스테이션 로 이동할 때 와 사이의 중간 스테이션을 거쳐야 할 수도 있다는 점에 유의하자. 존이 그러한 스테이션 가 존재하는지 알아낼 수 있도록 도와주자.
입력
첫 번째 줄에는 가공 스테이션의 수를 나타내는 정수 이 주어진다. 다음 개의 줄에는 이고 인 두 정수 와 가 공백으로 구분되어 주어진다. 이는 스테이션 에서 스테이션 로 이동하는 컨베이어 벨트가 있어 에서 방향으로만 이동할 수 있음을 나타낸다.
출력
임의의 다른 스테이션에서 스테이션 로 이동할 수 있는 스테이션 가 존재하면 그러한 중 가장 작은 것을 출력한다. 그렇지 않으면 을 출력한다.