← 返回题目列表

AtCoder · agc027_f

F. 嫁接

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

分数: 1900 点

问题陈述

Snuke 发现了两棵树 A 和 B,每个都有 N 顶点编号 1 to N。 的 i第边缘 A 连接顶点 a_i 和 b_i,以及 j第边缘 B 连接顶点 c_j 和 d_j。 另外,所有顶点 A 最初漆成白色。

Snuke 想要执行以下操作 A 零次或多次,以便 A 与 B:

  • 选择一个涂成白色的叶顶点。 (令该顶点为 v.)
  • 删除入射到的边 v,并添加一条连接的新边 v 到另一个顶点。
  • 油漆 v 黑色。

确定是否 A 可以与 B,忽略颜色。如果答案是肯定的,请找出所需的最少操作数。

你被给予 T 此类案例。找出每个问题的答案。

约束

  • 1 \leq T \leq 20
  • 3 \leq N \leq 50
  • 1 \leq a_i,b_i,c_i,d_i \leq N
  • 所有给定的图都是树。

输入

输入由标准输入按以下格式给出:

T
case_1
:
case_{T}

每个案例均按以下格式给出:

N
a_1 b_1
:
a_{N-1} b_{N-1}
c_1 d_1
:
c_{N-1} d_{N-1}

输出

对于每种情况,如果 A 可以与 B 忽略颜色,打印所需的最少操作次数,并打印 -1 如果不能的话。


样本输入 1

2
3
1 2
2 3
1 3
3 2
6
1 2
2 3
3 4
4 5
5 6
1 2
2 4
4 3
3 5
5 6

示例输出 1

1
-1
  • 每种情况下的图表如下所示。
  • 万一 1, A 可以与 B 通过选择顶点 1,删除连接的边缘 1 和 2,并添加一条连接边 1 和 3。注意顶点 2 不是叶顶点,因此无法选择。
3f020b4a4e883680357cc55adb571fbc.png

示例输入 2

3
8
2 7
4 8
8 6
7 1
7 3
5 7
7 8
4 2
5 2
1 2
8 1
3 2
2 6
2 7
4
1 2
2 3
3 4
3 4
2 1
3 2
9
5 3
4 3
9 3
6 8
2 3
1 3
3 8
1 7
4 1
2 8
9 6
3 6
3 5
1 8
9 7
1 6

示例输出 2

6
0
7
  • A 可能与 B 从头开始。