单向排水汇点

普及-⏱ 1000ms💾 256MB#P3276🏷️ Floyd传递闭包图论

题目描述

厂区有 $N$ 个泵站(编号 $1 \sim N$)与 $N-1$ 条管道(任意两泵站间沿管道双向可绕通,即底层连通结构是一棵树)。 每条管道后来被指定了单向流通方向。现在想知道:是否存在某个泵站 $i$, 使得从其余每个泵站出发沿单向管道都能到达 $i$。若存在,输出最小的编号 $i$;否则输出 $-1$。

输入格式

第一行一个整数 $N$。 以下 $N-1$ 行每行两个整数 $a_i, b_i$:一条从 $a_i$ 指向 $b_i$ 的单向管道($a_i \neq b_i$)。

输出格式

一行一个整数:满足条件的最小泵站编号,不存在则输出 $-1$。

数据范围

None

样例输入 #1
3
1 2
3 2
样例输出 #1
2
样例输入 #2
1
样例输出 #2
1