分数: 1400 点
问题陈述
Sigma 和 Sugim 正在玩游戏。
游戏在图表上进行 N 顶点编号 1 通过 N。该图有 N-1 红色边缘和 N-1 蓝色边缘,以及 N-1 每种颜色的边形成一棵树。红色边缘由整数对表示 (a_i, b_i),蓝色边缘由整数对表示 (c_i, d_i).
每个玩家都有自己的棋子。最初,西格玛的棋子位于顶点 X,Sugim 的棋子位于顶点 Y.
游戏按回合进行,回合从回合开始编号 1。西格玛轮流 1, 3, 5, ...,Sugim 轮流 2, 4, 6, ....
在每个回合中,当前玩家要么移动他的棋子,要么什么也不做。在这里,西格玛只能将他的棋子移动到通过红边直接连接到当前顶点的顶点。同样,Sugim 只能将他的棋子移动到通过蓝色边直接连接到当前顶点的顶点。
当两块棋子到达同一顶点时,游戏立即结束。如果依次操作后游戏结束 i,让 i 是游戏中的总回合数。
Sigma 的目标是使总匝数尽可能大,而 Sugim 的目标是使其尽可能小。
假设两个玩家都以最佳方式实现各自的目标,确定游戏是否会在有限轮数内结束。如果答案是肯定的,求游戏的回合数。 每种颜色(红色和蓝色)的
约束
- 2 ≦ N ≦ 200,000
- 1 ≦ X, Y ≦ N
- X \neq Y
- 1 ≦ a_i, b_i, c_i, d_i ≦ N
- 的 N-1 边形成一棵树。
输入
输入由标准输入按以下格式给出:
N X Y
a_1 b_1
a_2 b_2
:
a_{N-1} b_{N-1}
c_1 d_1
c_2 d_2
:
c_{N-1} d_{N-1}
输出
如果游戏将在有限回合数内结束,则打印回合数。
否则,打印 -1.
样本输入 1
4 1 2 1 2 1 3 1 4 2 1 2 3 1 4
示例输出 1
4

示例输入 2
3 3 1 1 2 2 3 1 2 2 3
示例输出 2
4

示例输入 3
4 1 2 1 2 3 4 2 4 1 2 3 4 1 3
示例输出 3
2

示例输入 4
4 2 1 1 2 3 4 2 4 1 2 3 4 1 3
示例输出 4
-1
示例输入 5
5 1 2 1 2 1 3 1 4 4 5 2 1 1 3 1 5 5 4
示例输出 5
6