우유 공장

면접 대비

시간 제한2초메모리 제한512 MB

요약
방향 트리에서 모든 다른 정점에서 도달할 수 있는 가장 작은 정점을 찾고, 그런 정점이 없으면 -1을 출력한다.
난이도

보통10점 중 4점

유형
그래프, DFS, 트리, 구현
정답자
아직 제출이 없습니다

문제

우유 사업이 잘 되고 있다! 농부 존의 우유 가공 공장은 NN개의 가공 스테이션으로 이루어져 있고, 스테이션에는 1…N1 \ldots N의 번호가 붙어 있다 (1≤N≤1001 \leq N \leq 100). 또한 N−1N-1개의 통로가 있으며, 각 통로는 두 스테이션을 연결한다. 통로를 만드는 데는 돈이 많이 들기 때문에, 존은 어떤 스테이션에서 출발해도 다른 모든 스테이션에 도달할 수 있도록 최소 개수의 통로만 설치했다.

효율을 높이기 위해 존은 모든 통로에 컨베이어 벨트를 설치했다. 그런데 각 컨베이어 벨트가 한 방향으로만 움직인다는 사실을 너무 늦게 깨달았다. 이제 통로를 따라 이동하는 것은 한 방향으로만 가능하다! 따라서 더 이상 어떤 스테이션에서든 다른 어떤 스테이션으로든 갈 수 있는 것은 아니다.

그래도 존은 모든 다른 스테이션에서 스테이션 ii로 결국 이동할 수 있는 스테이션 ii가 적어도 하나 존재한다면 모든 것이 끝난 것은 아니라고 생각한다. 다른 임의의 스테이션 jj에서 스테이션 ii로 이동할 때 ii와 jj 사이의 중간 스테이션을 거쳐야 할 수도 있다는 점에 유의하자. 존이 그러한 스테이션 ii가 존재하는지 알아낼 수 있도록 도와주자.

입력

첫 번째 줄에는 가공 스테이션의 수를 나타내는 정수 NN이 주어진다. 다음 N−1N-1개의 줄에는 1≤a_i,b_i≤N1 \leq a\_i, b\_i \leq N이고 a_i≠b_ia\_i \neq b\_i인 두 정수 a_ia\_i와 b_ib\_i가 공백으로 구분되어 주어진다. 이는 스테이션 a_ia\_i에서 스테이션 b_ib\_i로 이동하는 컨베이어 벨트가 있어 a_ia\_i에서 b_ib\_i 방향으로만 이동할 수 있음을 나타낸다.

출력

임의의 다른 스테이션에서 스테이션 ii로 이동할 수 있는 스테이션 ii가 존재하면 그러한 ii 중 가장 작은 것을 출력한다. 그렇지 않으면 −1-1을 출력한다.

예제1

  1. 예제 1

    입력
    3
    1 2
    3 2
    
    예상 출력
    2