CF2187F1 Al Fine (Maximizing Version)

这是该问题的最大化版本。与其他版本的不同之处在于，在本版本中，你需要找到所有“公共树”中可能的最大深度。此外，本版本对于 $n$ 的限制更大。只有在你解决了所有版本的本题后，才能进行 hack。 在圣诞节，Tortinita 和 Arietta 各自都得到了一个圣诞树。巧合的是，她们的树拥有完全相同的性质：两棵树均有 $n+1$ 个结点，且都以结点 $0$ 作为根节点。在她们寄给你的圣诞贺卡中，会在祝福语后附上一个各自的树的 DFS 序列。回忆一下，DFS 序列是通过如下伪代码生成的。 ``` dfs_order = [] def dfs(v): dfs_order.append(v) pick an arbitrary permutation s of children of v for child in s: dfs(child) dfs(root) ``` 设 Tortinita 的树的 DFS 序列为 $a_0, a_1, \ldots, a_n$，Arietta 的树的 DFS 序列为 $b_0, b_1, \ldots, b_n$。你注意到 $a_0=b_0=0$，而且因为她们是双胞胎姐妹，你想知道她们是否可能选到完全相同的树。你还觉得，姐妹们的圣诞树绝不会选平凡的结构。因此，你希望求出所有公共树中可能的最大深度 $^{\text{∗}}$。 $^{\text{∗}}$ 树的深度定义为任意节点到根节点的简单路径上的最大边数。

每组测试数据包含多组测试用例。第一行包含测试用例的数量 $t$（$1\leq t \leq 10^4$）。接下来为每组测试用例的描述。 每组测试用例的第一行包含一个整数 $n$（$2\leq n \leq 10^6$）。 第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$（$1 \leq a_i \leq n$）。 第三行包含 $n$ 个整数 $b_1, b_2, \cdots, b_n$（$1 \leq b_i \leq n$）。 保证序列 $a$ 和 $b$ 均无重复元素。 保证所有测试用例中 $n$ 的和不超过 $10^6$。

对于每组测试用例，输出一个整数——所有公共树中可能的最大深度。

在第一个测试用例中，$a$ 和 $b$ 相同。考虑一颗链式树，边为 $(0,1)$ 和 $(1,2)$，它能产生这两个 DFS 序列，其深度为 $2$。可以证明在所有公共树中最大深度为 $2$。 在第二个测试用例中，考虑一棵星形树，边为 $(0,1)$ 和 $(0,2)$，其深度为 $1$。可以证明最大深度为 $1$。 在第三个测试用例中，下图是深度最大的方案之一，深度为 $3$。  由 ChatGPT 5 翻译