AT_agc027_f [AGC027F] Grafting

すぬけ君发现了两棵有 $N$ 个顶点的树 $A$ 和 $B$，每个顶点编号为 $1$ 到 $N$。树 $A$ 的第 $i$ 条边连接顶点 $a_i$ 和 $b_i$，树 $B$ 的第 $j$ 条边连接顶点 $c_j$ 和 $d_j$。所有顶点初始时都被涂成白色。 すぬけ君可以对 $A$ 进行如下操作若干次（可以为 $0$ 次），希望将 $A$ 变为与 $B$ 完全相同。 - 选择一个被白色涂色的**叶子**（记为 $v$）。 - 移除与 $v$ 相连的边，并添加一条 $v$ 与另一个顶点相连的新边。 - 将 $v$ 涂成黑色。 请判断是否可以通过上述操作将 $A$ 变为 $B$，如果可以，求所需操作次数的最小值。判断两棵树是否一致时，不考虑顶点的颜色。 有 $T$ 组测试数据，请分别输出每组的答案。

输入按以下格式从标准输入读入。 > $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 \leq T \leq 20$ - $3 \leq N \leq 50$ - $1 \leq a_i, b_i, c_i, d_i \leq N$ - 输入的图均为树 ### 样例解释 1 - 每组数据给出的图如下图所示。对于第 $1$ 组，可以选择顶点 $1$，移除 $1$ 与 $2$ 的边，并添加 $1$ 与 $3$ 的边，即可将 $A$ 变为 $B$。注意，顶点 $2$ 不是叶子，不能被选择。  ### 样例解释 2 - 有时 $A$ 和 $B$ 已经一致。 由 ChatGPT 4.1 翻译