当前没有测试数据。

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

空白这一次的来到了森精种的家园，精灵都喜欢贴近大自然，喜欢住在树洞里，所以他们的家园是一

棵神树！他们非常喜欢艺术，就是说喜欢改造他们所居住的神树！

他们现在居住的树的形态可以描述成一颗有 $n$ 个树洞的树 $A$，一共有 $n$ ? 1 条边连接，使得树洞两

两可以到达，且树洞根据编号是可区分的。

现在菲尔带来了下一代神树的设计图，假设为树 $B$，现在她想考一考空白，如果根据如下规则调整神

树，至少需要调整多少次才可以将 $A$ 树变成 $B$ 树。

一次调整可以选择一个节点 $x$，然后将 $x$ 以及和 $x$ 相邻的节点（也就是有边直接相连的节点）打上魔

法标记，然后断开 $x$ 的所有邻边，然后再在所有打上魔法标记的点直接添加若干条新边，形成一棵新

的树，同时魔法标记消失。

输入

第一行一个正整数 $n$，表示树的大小。

接下来 $n$ - 1 行，每行两个整数 $u$, $v$，表示 $A$ 树上的边 ($u$, $v$)。

然后还有 $n$ - 1 行，每行两个整数 $u$, $v$，表示 $B$ 树上的边 ($u$, $v$)。

输出

一行一个整数表示最少调整次数。

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

1

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

2

样例 $1$ 解释：

可以选择 $x=3$ 进行调整，这时候 $1,3,4,5$ 都被打上了魔法标记。

删去了边 (3, 1)，(3, 4)，(3, 5)，添加边 (1, 4)，(4, 3)，(3, 5) 。

数据范围限制

对于 $20\%$ 的数据：$1≤n≤8$

对于 $60\%$ 的数据：$1≤n≤5000$

对于 $100\%$ 的数据：$1\le n\le 10^6$