파일 업로드

우유 공장 통로

profile
실행 시간 제한메모리 제한
2 초512 MB
📃 해결할 문제

지화의 우유 사업이 활발해지고 있습니다! 지화의 우유 가공 공장은 NN개의 처리 스테이션으로 구성되어 있으며, 편리하게 번호 1N1 \ldots N (1N1001 \leq N \leq 100), 그리고 N1N-1 통로를 가지고 있습니다. 각 통로는 일부 스테이션들 사이를 연결합니다. (통로는 비싸므로, 지화는 최소한의 통로만 사용하기로 결정했습니다).

효율성을 높이기 위해 지화는 모든 다리에 컨베이어 벨트를 설치합니다. 그런데 각 컨베이어 벨트는 한 방향으로만 움직이기 때문에, 각 통로를 따라 이동할 수 있는 방향은 한 방향뿐입니다! 이제, 모든 스테이션에서 다른 모든 스테이션으로 이동할 수 있다고 말할 수 없습니다.

하지만, 지화는 다른 모든 스테이션에서 스테이션 ii까지 이동할 수 있는 스테이션 ii가 하나 이상 있다면 모든 스테이션을 이동할 수 있다고 생각하빈다. 여기서 다른 임의의 스테이션 jj에서 스테이션 ii로 이동한다는 것은 iijj 사이의 중간 역을 통과해야 할 수도 있다는 점에 유의하세요. 지화가 그러한 스테이션 ii가 존재하는 지 알아내도록 도와주세요.

💻 입력

첫 번째 줄은 처리 스테이션의 수인 정수 NN를 나타냅니다. 그 다음의 N1N-1줄은 각각 띄어쓰기로 구분된 두 개의 정수 aia_ibib_i를 표시하며 1ai,biN1 \leq a_i, b_i \leq N 그리고 aibia_i \neq b_i. 이것은 스테이션 aia_i에서 스테이션 bib_i로 이동가능한 컨베이어 벨트가 있음을 나타냅니다. 이동은 aia_i에서 bib_i로만 가능합니다.

🖨️ 출력

모든 다른 스테이션에서 특정 스테이션 ii로 이동할 수 있다면, 그런 ii 중 가장 작은 값을 출력하세요. 그런 스테이션이 없다면, 1-1을 출력하세요.


💻 예제 입력 1
3
1 2
3 2
🖨️ 예제 출력 1
2

출처: USACO 2019 US Open Contest, Bronze Problem 2. Milk Factory