Problem5774--奶牛工厂

5774: 奶牛工厂

Time Limit: 1.000 Sec  Memory Limit: 256 MB
Submit: 18  Solved: 13
[Submit] [Status] [Web Board] [Creator:]

Description

牛奶生意正红红火火!Farmer John的牛奶加工厂内有NN个加工站,编号为1…N(1≤N≤100)1N1N100,以及N−1N1条通道,每条连接某两个加工站。(通道建设很昂贵,所以Farmer John选择使用了最小数量的通道,使得从每个加工站出发都可以到达所有其他加工站)。 为了创新和提升效率,Farmer John在每条通道上安装了传送带。不幸的是,当他意识到传送带是单向的已经太晚了,现在每条通道只能沿着一个方向通行了!所以现在的情况不再是从每个加工站出发都能够到达其他加工站了。

然而,Farmer John认为事情可能还不算完全失败,只要至少还存在一个加工站ii满足从其他每个加工站出发都可以到达加工站ii。注意从其他任意一个加工站jj前往加工站ii可能会经过iijj之间的一些中间站点。请帮助Farmer John求出是否存在这样的加工站ii



Input

输入的第一行包含一个整数NN,为加工站的数量。以下N−1N1行每行包含两个空格分隔的整数aiaibibi,满足1≤ai,bi≤N1ai,biN以及ai≠biai=bi。这表示有一条从加工站aiai向加工站bibi移动的传送带,仅允许沿从aiaibibi的方向移动。

Output

如果存在加工站i满足可以从任意其他加工站出发都可以到达加工站ii,输出最小的满足条件的ii。否则,输出−1。

Sample Input

3
1 2
3 2

Sample Output

2

Source/Category

 

[Submit] [Status]