USACO 2019 US Open Contest, Bronze Problem 2 Milk Factory
The milk business is booming! Farmer John's milk processing factory consists of NN processing stations, conveniently numbered 1…N1…N (1≤N≤1001≤N≤100), and N−1N−1 walkways, each connecting some pair of stations. (Walkways are expensive, so Farmer John has elected to use the minimum number of walkways so that one can eventually reach any station starting from any other station).
To try and improve efficiency, Farmer John installs a conveyor belt in each of its walkways. Unfortunately, he realizes too late that each conveyor belt only moves one way, so now travel along each walkway is only possible in a single direction! Now, it is no longer the case that one can travel from any station to any other station.
However, Farmer John thinks that all may not be lost, so long as there is at least one station ii such that one can eventually travel to station ii from every other station. Note that traveling to station ii from another arbitrary station jj may involve traveling through intermediate stations between ii and jj. Please help Farmer John figure out if such a station ii exists.
INPUT FORMAT (file factory.in):
The first line contains an integer NN, the number of processing stations. Each of the next N−1N−1 lines contains two space-separated integers aiai and bibi with 1≤ai,bi≤N1≤ai,bi≤N and ai≠biai≠bi. This indicates that there is a conveyor belt that moves from station aiai to station bibi, allowing travel only in the direction from aiai to bibi.
OUTPUT FORMAT (file factory.out):
If there exists a station ii such that one can walk to station ii from any other station, then output the minimal such ii. Otherwise, output −1−1.
SAMPLE INPUT:
3
1 2
3 2
SAMPLE OUTPUT:
2
Problem credits: Dhruv Rohatgi
中文版
牛奶生意正红红火火！Farmer John的牛奶加工厂内有NN个加工站，编号为1…N1…N（1≤N≤1001≤N≤100），以及N−1N−1条通道，每条连接某两个加工站。（通道建设很昂贵，所以Farmer John选择使用了最小数量的通道，使得从每个加工站出发都可以到达所有其他加工站）。
为了创新和提升效率，Farmer John在每条通道上安装了传送带。不幸的是，当他意识到传送带是单向的已经太晚了，现在每条通道只能沿着一个方向通行了！所以现在的情况不再是从每个加工站出发都能够到达其他加工站了。
然而，Farmer John认为事情可能还不算完全失败，只要至少还存在一个加工站ii满足从其他每个加工站出发都可以到达加工站ii。注意从其他任意一个加工站jj前往加工站ii可能会经过ii和jj之间的一些中间站点。请帮助Farmer John求出是否存在这样的加工站ii。
输入格式（文件名：factory.in）：
输入的第一行包含一个整数NN，为加工站的数量。以下N−1N−1行每行包含两个空格分隔的整数aiai和bibi，满足1≤ai,bi≤N1≤ai,bi≤N以及ai≠biai≠bi。这表示有一条从加工站aiai向加工站bibi移动的传送带，仅允许沿从aiai到bibi的方向移动。
输出格式（文件名：factory.out）：
如果存在加工站ii满足可以从任意其他加工站出发都可以到达加工站ii，输出最小的满足条件的ii。否则，输出−1−1。
输出样例：
3
1 2
3 2
输出样例：
2
供题：Dhruv Rohatgi
计算机
翰林USACO课程体系流程图
国际竞赛真题资料-点击免费领取！
美高学分项目重磅来袭！立即了解
AMC8备考管家服务全新上线！
