题目描述

Farmer John 有 N 个农场，编号为 1 ~ N。

有若干条无向道路，每条路连接两个不同的农场。任意两个农场都是可以互达的。

众所周知，奶牛是喜欢串门的。

特别是住在农场 A 的奶牛和住在农场 B 的奶牛，它俩串门实在太频繁了。

John 觉得这已经影响了农场的正常运作。

于是他准备封锁一个农场。

如果一个农场被封锁，那么这个农场将不允许有牛经过。

当然，为了不让奶牛看出来 John 在故意针对它们，John 不会封锁农场 A，也不会封锁农场 B。

现在，John 想知道，他应该封锁哪一个农场才能阻止两头奶牛串门？

输入格式

第一行：一个整数 N

接下来若干行：每行两个整数 u, v 表示农场 u 和农场 v 之间有一条道路。如果 u=v=0 则表示道路描述完毕。

最后一行：两个整数 A, B （数据保证 A ≠ B）。

输出格式

一个整数，表示答案。如果有多个农场满足条件，输出编号最小的那个；如果封锁任意一个农场均不能阻止奶牛串门，则输出 -1。

样例输入

5
1 2
2 3
3 4
4 2
3 5
0 0
5 1

样例输出

2

提示

50分 的数据：包含 10 个测试点，全部满足 $1 ≤ N ≤ 100$，其中有 1 个测试点（5分）所有农场和道路构成一棵树。

另外 50分 的数据：包含 3 个测试点，全部满足 $1 ≤ N ≤ 100000$，边数不超过 $500000$，其中有 1 个测试点（10分）所有农场和道路构成一棵树。