Milk Factory

题目描述

牛奶生意蒸蒸日上！Farmer John 的牛奶加工厂由 $N$ 个加工站组成，方便起见编号为 $1 \ldots N$（$1 \leq N \leq 100$），以及 $N-1$ 条步道，每条步道连接一对站点。（步道造价昂贵，因此 Farmer John 选择使用最少数量的步道，使得从任意一个站点出发最终都能到达任何其他站点。）

为了提高效率，Farmer John 在每条步道上安装了一条传送带。不幸的是，他发现得太晚了：每条传送带只能单向移动，因此现在沿每条步道的通行只能在一个方向上进行！现在，不再能从任意站点到达任意其他站点。

然而，Farmer John 认为只要至少存在一个站点 $i$，使得从其他每一个站点最终都能到达站点 $i$，一切也许还不算完。注意，从另一个任意站点 $j$ 前往站点 $i$ 可能需要经过位于 $i$ 与 $j$ 之间的中间站点。请帮助 Farmer John 判断是否存在这样的站点 $i$。

输入格式

第一行包含一个整数 $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$。

3
1 2
3 2

2

提示

题目致谢：Dhruv Rohatgi

标签: USACO|2019|Bronze

来源

USACO|2019|Bronze