K. DFS序对(Hard Version)
time limit per test
3 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

本题定义、输入格式、输出格式均与简单版本相同，在这个版本中，$$$n\le 5000$$$，但你需要构造出符合条件的树且每个节点深度总和最大化的方案。

排列：长度为 $$$n$$$ 的定义为由 $$$1\sim n$$$ 以不同顺序组成的序列，且每个元素恰好出现一次。例如 $$$[2,1,3],[2,4,1,3]$$$ 都是排列，而 $$$[4,1,2]$$$ 不是排列，因为 $$$3$$$ 没有出现，$$$[1,2,3,2]$$$ 不是排列，因为 $$$2$$$ 出现了 $$$2$$$ 次。

树的dfs序：对一棵树进行深度优先遍历（DFS），每当我们第一次访问某个节点时，就将该节点编号加入序列中。得到的访问顺序称为DFS 序。例如：

对于给定的树，$$$[1,2,3,4,5,6,7],[1,3,4,7,5,6,2],[3,4,1,2,7,5,6]$$$ 均是这棵树能形成的 dfs 序。$$$[1,2,4,3,5,6,7]$$$ 不是这棵树的 dfs 序，因为 $$$2$$$ 号点到 $$$4$$$ 号点存在未访问的 $$$3$$$ 号点，$$$[1,2,3,4,5,7,6]$$$ 不是这棵树的 dfs 序，因为子树 $$$5$$$ 不满足 DFS 遍历性质。

树的深度：我们定义根节点的深度为 $$$1$$$。对于其他任意节点 $$$u$$$，其深度为 $$$u$$$ 的父节点的深度加 $$$1$$$。

现在，给定 $$$2$$$ 个 $$$1\sim n$$$ 组成的排列，现在要求你构造包含这两种dfs序的树，且使得每个节点深度总和最大化。可以证明无论序列如何，总是存在对应的树。

Input

第一行输入一个正整数 $$$T(1\le T\le 10^3)$$$，表示测试组数。

接下来每组测试中：

  • 第一行输入一个正整数 $$$n(3\le n\le 5000)$$$
  • 第二行输入一个长度为 $$$n$$$ 的排列 $$$p_1,p_2,\cdots,p_n$$$，表示树的其中一种 dfs 序。
  • 第三行输入一个长度为 $$$n$$$ 的排列 $$$q_1,q_2,\cdots,q_n$$$，表示树的另一种 dfs 序。
  • 此外，保证 $$$p_1=1,q_1=1$$$。

此外，数据保证所有测试点的 $$$n$$$ 之和不超过 $$$5000$$$。

Output

对于每组数据，输出共 $$$n-1$$$ 行，使其形成一棵树，每行输出 $$$2$$$ 个正整数 $$$u,v(1\le u,v\le n,u\neq v)$$$，表示一条边。

如果存在多种合法解，输出其中任意一种即可。

Example
Input
3
6
1 2 3 6 5 4
1 2 3 4 5 6
8
1 2 8 5 7 4 6 3
1 6 3 4 5 7 2 8
7
1 2 3 4 5 6 7
1 3 4 7 5 6 2
Output
1 2
2 3
3 6
3 5
3 4
1 2
2 8
1 5
5 7
1 4
1 6
6 3
1 2
1 3
3 4
4 5
5 6
4 7