分数: 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 不是叶顶点,因此无法选择。
示例输入 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 从头开始。