← 返回题目列表

AtCoder · agc005_e

E. Sugigma:对决

中文机器翻译题面 查看原题

分数: 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