Soroush 和 Keshi 在 $$$n$$$ 顶点上各有一棵有标签且有根的树。它们的两棵树都以顶点 $$$1$$$ 为根。
索鲁什和克什曾经处于战争状态。经过数十年无休止的战斗,他们终于成为盟友,准备进行 Codeforces 回合。为了庆祝这一幸运事件,他们决定在 $$$n$$$ 个顶点上制作一个纪念图。
如果满足以下两个条件,它们会在纪念图中的顶点 $$$u$$$ 和 $$$v$$$ 之间添加一条边:
- $$$u$$$ 或 $$$v$$$ 之一是 Soroush 树中另一个的祖先。
- $$$u$$$ 或 $$$v$$$ 都不是 Keshi 树中另一个的祖先。
这里,如果 $$$u$$$ 位于从 $$$1$$$(根)到 $$$v$$$ 的路径上,则顶点 $$$u$$$ 被视为顶点 $$$v$$$ 的祖先。
Mashtali 突然冒出来,无缘无故地试图在纪念图中找到最大的派系。他失败了,因为图表太大了。
通过找到纪念图中最大派系的大小来帮助 Mashtali。
提醒一下,团是图的顶点的子集,每两个顶点由一条边连接。
输入
第一行包含一个整数 $$$t$$$ $$$(1\le t\le 3 \cdot 10^5)$$$ — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ $$$(2\le n\le 3 \cdot 10^5)$$$。
每个测试用例的第二行包含 $$$n-1$$$ 整数 $$$a_2, \ldots, a_n$$$ $$$(1 \le a_i < i)$$$,$$$a_i$$$ 是 Soroush 树中顶点 $$$i$$$ 的父节点。
每个测试用例的第三行包含 $$$n-1$$$ 整数 $$$b_2, \ldots, b_n$$$ $$$(1 \le b_i < i)$$$,$$$b_i$$$ 是 Keshi 树中顶点 $$$i$$$ 的父节点。
保证给定的图是树。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数——纪念图中最大团的大小。
示例
输入 #1
4 4 1 2 3 1 2 3 5 1 2 3 4 1 1 1 1 6 1 1 1 1 2 1 2 1 2 2 7 1 1 3 4 4 5 1 2 1 4 2 5
输出 #1
1 4 1 3
注意
在第一个和第三个测试用例中,您可以选择任何顶点。
在第二个测试用例中,最大派系之一是 $$$\{2, 3, 4, 5\}$$$。
在第四个测试用例中,最大派系之一是 $$$\{3, 4, 6\}$$$。