CF2187F1.Al Fine (Maximizing Version)

This is the maximizing version of the problem. The difference between the versions is that in this version, you need to find the maximum possible depth among all common trees. Also, the constraint on $n$ in this version is larger. You can hack only if you solved all versions of this problem.

For Christmas, Tortinita and Arietta each get a Christmas tree. Coincidentally, their trees share the same properties: both have $n+1$ vertices and are rooted at vertex $0$. In their Christmas card to you, each of them appends a DFS order sequence of their tree after their greetings. Recall that a DFS order sequence is generated by the following pseudocode.

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)

Let the DFS order sequence of Tortinita's tree be $a_0, a_1, \ldots, a_n$ and that of Arietta's tree be $b_0, b_1, \ldots, b_n$. You observe that $a_0 = b_0 = 0$, and since they are twin sisters, you wonder if they could have the exact same tree. You also feel that for their Christmas tree, the sisters would not choose a trivial structure. Therefore, you want to find the maximum possible depth$^{\text{∗}}$ among all common trees for both sequences.

$^{\text{∗}}$The depth of a tree is defined as the maximum number of edges on a simple path from any node to the root.

这是该问题的最大化版本。两个版本的区别在于：在本版本中，你需要找出所有公共树中可能的最大深度。此外，本版本中对 $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{∗}}$树的深度定义为：从任意节点到根节点的简单路径上所含边数的最大值。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains one integer $n$ ($2 \le n \le 10^6$).

The second line of each test case contains $n$ integers $a_1, a_2, \cdots, a_n$ ($1 \le a_i \le n$).

The third line of each test case contains $n$ integers $b_1, b_2, \cdots, b_n$ ($1 \le b_i \le n$).

It is guaranteed that neither sequence $a$ nor $b$ contains duplicates.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 10^6$）。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$（$1 \le a_i \le n$）。

每个测试用例的第三行包含 $n$ 个整数 $b_1, b_2, \cdots, b_n$（$1 \le b_i \le n$）。

保证序列 $a$ 和序列 $b$ 均不包含重复元素。

保证所有测试用例中 $n$ 的总和不超过 $10^6$。

For each test case, output one integer — the maximum possible depth among all common trees.

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

In the first test case, $a$ and $b$ are the same. Consider a link tree with edges $(0,1)$ and $(1,2)$; it can give either DFS order sequence, and its depth is $2$. It can be shown that $2$ is the maximum depth among all possible common trees.

In the second test case, consider a star-shaped tree with edges $(0,1)$ and $(0,2)$, whose depth is $1$. It can be shown that $1$ is the maximum depth among all possible common trees.

In the third test case, the figure shows one of the trees with the maximum depth of $3$.

在第一个测试用例中，$a$ 和 $b$ 相同。考虑一棵具有边 $(0,1)$ 和 $(1,2)$ 的链状树；该树可生成任意一种 DFS 序列，且其深度为 $2$。可以证明，$2$ 是所有可能的公共树中最大的深度。

在第二个测试用例中，考虑一棵星形树，其边为 $(0,1)$ 和 $(0,2)$，深度为 $1$。可以证明，$1$ 是所有可能的公共树中最大的深度。

在第三个测试用例中，下图展示了一棵深度达到最大值 $3$ 的树。