Berland 宫殿中的电网由 2 个电网组成:主电网和备用电网。宫殿里的电线都是用昂贵的材料制成的,所以卖掉一些是个好主意!
每个网格(主网格和备用网格)都有一个头节点(其编号为$$$1$$$)。其他每个节点都从头节点获取电力。每个节点都可以通过唯一的路径从头节点到达。此外,两个电网都有 $$$n$$$ 个节点,这些节点不会进一步传播电力。
换句话说,每个网格都是 $$$n$$$ 个叶子上的有根有向树,根节点为 $$$1$$$。每棵树都有独立的枚举,一个网格的节点不与另一个网格的节点连接。
此外,宫殿有 $$$n$$$ 电气设备。每台设备分别与主电网的一个节点和备用电网的一个节点连接。设备仅与节点连接,电力不会从节点进一步传播(这些节点是树叶)。每个网格的叶子都与一个设备连接。
在此示例中,主网格包含 $$$6$$$ 节点(顶部树),备用网格包含 $$$4$$$ 节点(下部树)。有 $$$3$$$ 设备,数字为蓝色。
保证整个网格(两个网格和$$$n$$$设备)可以这样显示(如上图所示):
- 主网格是一棵顶树,其电线的方向是“从上到下”,
- 储备网格是一棵较低的树,其电线“从下到上”,
- 设备 — 两个网格之间的水平行,从左到右编号从 $$$1$$$ 到 $$$n$$$,
- 节点之间的电线不相交。
形式上,对于每棵树,存在从编号为 $$$1$$$ 的节点开始的深度优先搜索,该搜索按照连接到设备 $$$1, 2, \dots, n$$$ 的顺序访问叶子(首先是连接到设备 $$$1$$$ 的节点,然后是连接到设备 $$$2$$$ 的节点,等等)。
商人想要出售(移除)最大数量的电线,以便每个设备至少由一个电网(主电网或备用电网)供电。换句话说,对于每个设备应该存在至少一条到头节点(在主网格或备用网格中)的路径,该路径仅包含来自一个网格的节点。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 1000$$$) — 宫殿中的设备数量。
下一行包含一个整数 $$$a$$$ ($$$1 + n \le a \le 1000 + n$$$) — 主网格中的节点数量。
下一行包含 $$$a - 1$$$ 整数 $$$p_i$$$ ($$$1 \le p_i \le a$$$)。每个整数 $$$p_i$$$ 表示主网格包含从第 $$$p_i$$$ 个节点到第 $$$(i + 1)$$$ 个节点的连线。
下一行包含 $$$n$$$ 整数 $$$x_i$$$ ($$$1 \le x_i \le a$$$) — 主网格中连接到第 $$$i$$$ 设备的节点编号。
下一行包含一个整数 $$$b$$$ ($$$1 + n \le b \le 1000 + n$$$) — 备用网格中的节点数量。
下一行包含 $$$b - 1$$$ 整数 $$$q_i$$$ ($$$1 \le q_i \le b$$$)。每个整数 $$$q_i$$$ 表示备用网格包含从第 $$$q_i$$$ 个节点到第 $$$(i + 1)$$$ 个节点的连线。
下一行包含 $$$n$$$ 整数 $$$y_i$$$ ($$$1 \le y_i \le b$$$) — 备用网格中连接到第 $$$i$$$ 设备的节点编号。
保证每个网格都是一棵树,它恰好有 $$$n$$$ 叶子,并且每个叶子都与一个设备连接。此外,还可以保证,对于每棵树,都存在从节点 $$$1$$$ 开始的深度优先搜索,该搜索按照与设备的连接顺序访问叶子。
输出
打印一个整数——为每个设备供电时可以切断的最大电线数量。
示例
输入 #1
3 6 4 1 1 4 2 6 5 3 4 1 1 1 3 4 2
输出 #1
5
输入 #2
4 6 4 4 1 1 1 3 2 6 5 6 6 6 1 1 1 5 4 3 2
输出 #2
6
输入 #3
5 14 1 1 11 2 14 14 13 7 12 2 5 6 1 9 8 3 10 4 16 1 1 9 9 2 5 10 1 14 3 7 11 6 12 2 8 16 13 4 15
输出 #3
17
注意
对于第一个示例,下图显示了一种可能的解决方案(可以移除的电线标记为红色):
第二个和第三个例子如下所示: