题目详情题解（0）讨论（0）提交记录（0）

AT_agc005_e.[AGC005E] Sugigma: The Showdown

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

しぐま君和すぎむ君决定玩一个游戏。

这个游戏在一个有 NN 个顶点的图上进行。顶点编号为 1,2,…,N1,2,\ldots,N。图中有 N−1N-1 条红色边和 N−1N-1 条蓝色边，且这两组边各自都构成一棵树。红色边由 (ai,bi)(a_i, b_i) 表示，蓝色边由 (ci,di)(c_i, d_i) 表示。

两人各自有一个棋子，しぐま君的棋子初始在顶点 XX，すぎむ君的棋子初始在顶点 YY。

游戏按回合进行，第 11、33、55、……回合由しぐま君行动，第 22、44、66、……回合由すぎむ君行动。

每个人在自己的回合可以选择移动自己的棋子或选择不动。但移动时有如下限制：しぐま君只能沿红色边移动到相邻顶点，すぎむ君只能沿蓝色边移动到相邻顶点。

如果两枚棋子到达同一个顶点，游戏立即结束。如果在第 ii 回合操作后游戏结束，则总回合数为 ii。

しぐま君希望让总回合数尽可能大，すぎむ君希望让总回合数尽可能小。

假设两人都以各自的目标采取最优策略，请判断游戏是否一定会结束。如果会结束，输出总回合数；如果永远不会结束，输出 −1-1。

输入格式

输入按以下格式从标准输入读入。

N X Y a1 b1 a2 b2 : aN−1 bN−1 c1 d1 c2 d2 : cN−1 dN−1N\ 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。

输入输出样例

  • 输入#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

说明/提示

限制条件

  • 2≤N≤200, ⁣0002 \leq N \leq 200,\!000
  • 1≤X,Y≤N1 \leq X, Y \leq N
  • X≠YX \neq Y
  • 1≤ai,bi,ci,di≤N1 \leq a_i, b_i, c_i, d_i \leq N
  • 红色边和蓝色边各自都构成一棵树

样例解释 1

样例解释 2

样例解释 3

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页