RiseOJ – 우유 공장

설명

우유 사업이 호황이다! 농부 존의 우유 가공 공장은 $1 \ldots N$ 으로 편리하게 번호가 붙은 $$N$$ 개의 가공 스테이션 ( $1 \leq N \leq 100$ )과, 각각 스테이션 쌍을 연결하는 $$N-1$$ 개의 통로로 이루어져 있다. (통로는 비싸기 때문에, 농부 존은 어떤 스테이션에서 출발하더라도 결국 다른 임의의 스테이션에 도달할 수 있도록 하는 최소 개수의 통로만 사용하기로 했다.)

효율을 높이기 위해, 농부 존은 각 통로에 컨베이어 벨트를 설치한다. 안타깝게도, 각 컨베이어 벨트가 한 방향으로만 움직인다는 사실을 너무 늦게 깨달아, 이제 각 통로를 따라 한 방향으로만 이동할 수 있게 되었다! 이제 임의의 스테이션에서 다른 임의의 스테이션으로 이동할 수 있다는 성질은 더 이상 성립하지 않는다.

하지만 농부 존은, 다른 모든 스테이션에서 결국 스테이션 $$i$$ 에 도달할 수 있는 스테이션 $$i$$ 가 적어도 하나 존재하기만 한다면 아직 희망이 있다고 생각한다. 임의의 다른 스테이션 $$j$$ 에서 스테이션 $$i$$ 로 이동할 때 $$i$$ 와 $$j$$ 사이의 중간 스테이션들을 거칠 수도 있다는 점에 유의하라. 그러한 스테이션 $$i$$ 가 존재하는지 농부 존이 알아내는 것을 도와주자.

문제 제공: Dhruv Rohatgi

제약

문제 제공: Dhruv Rohatgi

입력 형식

첫째 줄에 가공 스테이션의 수를 나타내는 정수 $$N$$ 이 주어진다. 다음 $$N-1$$ 개의 줄 각각에는 공백으로 구분된 두 정수 $$a_i$$ 와 $$b_i$$ 가 주어지며, $1 \leq a_i, b_i \leq N$ 이고 $a_i \neq b_i$ 이다. 이는 스테이션 $$a_i$$ 에서 스테이션 $$b_i$$ 로 움직이는 컨베이어 벨트가 있어, $$a_i$$ 에서 $$b_i$$ 방향으로만 이동할 수 있음을 나타낸다.

출력 형식

다른 임의의 스테이션에서 스테이션 $$i$$ 로 이동할 수 있는 스테이션 $$i$$ 가 존재한다면, 그러한 $$i$$ 중 최솟값을 출력한다. 존재하지 않으면 $$-1$$ 을 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 factory.in · 출력을 쓸 파일 factory.out

예제 1

입력

3
1 2
3 2

출력

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2018-2019 > US Open > Bronze

올림피아드 > USACO > 2018-2019 > US Open > Bronze

태그

JudgeUSACO

우유 공장

평가 및 의견

풀이 제출