题目描述

空白这一次的来到了森精种的家园，精灵都喜欢贴近大自然，喜欢住在树洞里，所以他们的家园是一棵神树！他们非常喜欢艺术，就是说喜欢改造他们所居住的神树！

他们现在居住的树的形态可以描述成一颗有 $n$ 个树洞的树 $A$，一共有 $n-1$ 条边连接，使得树洞两两可以到达，且树洞根据编号是可区分的。

现在菲尔带来了下一代神树的设计图，假设为树 $B$，现在她想考一考空白，如果根据如下规则调整神树，至少需要调整多少次才可以将 $A$ 树变成 $B$ 树。

一次调整可以选择一个节点 $x$，然后将 $x$ 以及和 $x$ 相邻的节点（也就是有边直接相连的节点）打上魔法标记，然后断开 $x$ 的所有邻边，然后再在所有打上魔法标记的点直接添加若干条新边，形成一棵新的树，同时魔法标记消失。

输入格式

第一行一个正整数 $n$，表示树的大小。 接下来 $n-1$ 行，每行两个整数 $u,v$，表示 $A$ 树上的边 $(u,v)$。 然后还有 $n-1$ 行，每行两个整数 $u,v$，表示 $A$ 树上的边 $(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\%$ 的数据，$n \le 8$。

对于 $60\%$ 的数据，$n \le 5000$。

对于 $100\%$ 的数据，$n \le 10^6$。