给你两棵有根树,每棵树由 $$$n$$$ 个顶点组成。树中的顶点编号从$$$1$$$到$$$n$$$,根是顶点$$$1$$$。
您可以执行以下操作:选择树以及其中的顶点$$$v$$$(树的根除外);将 $$$v$$$ 的子节点连接到 $$$v$$$ 的父节点,并从树中删除 $$$v$$$。
如果满足以下两个条件,则可以说两棵树相等:
- 两棵树中剩余顶点的集合相同;
- 对于每个未删除的顶点 $$$v$$$,其在第一棵树中的父节点与其在第二棵树中的父节点相同。
你的任务是计算上述操作的最少次数以使树相等。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 40$$$) — 树中的顶点数。
第二行包含 $$$n-1$$$ 整数 $$$a_2, a_3, \dots, a_n$$$ ($$$1 \le a_i \le n$$$),其中 $$$a_i$$$ 是第一棵树中第 $$$i$$$ 个顶点的父节点。顶点 $$$1$$$ 是根。
第三行包含 $$$n-1$$$ 整数 $$$b_2, b_3, \dots, b_n$$$ ($$$1 \le b_i \le n$$$),其中 $$$b_i$$$ 是第二棵树中第 $$$i$$$ 个顶点的父顶点。顶点 $$$1$$$ 是根。
输出
打印一个整数——为了使树相等而进行上述操作的最少次数。
示例
输入 #1
5 1 5 5 1 1 4 1 2
输出 #1
4
输入 #2
2 1 1
输出 #2
0
输入 #3
10 4 7 10 6 2 9 7 1 1 1 2 10 3 4 6 6 5 5
输出 #3
10