题目内容

在推荐系统中，两名用户分别给出了他们对 n 个项目的兴趣排序。每个用户的排序是一个长度为 n 的序列，恰好包含 1 到 n 每个编号一次。

系统希望生成一个推荐序列，这个序列必须同时是两名用户排序的子序列，且长度尽可能长；在长度最长的前提下，推荐序列的编号在字典序上要尽可能大（即希望优先展示编号较大的项目）。请你来设计这个推荐序列。

【定义】

• 子序列：从一个序列中删去若干元素（可以不删）后得到的新序列。
• 共同序列：如果序列 C 既是序列 A 的子序列，又是序列 B 的子序列，则称 C 为 A 与 B 的共同序列。
• 最长共同序列：长度最大的共同序列。
• 字典序比较：从两个序列的第一个元素开始逐个比较，直到出现第一个不同的位置；该位置上数值较大的序列字典序更大。

请你对于给定的两个序列 A 和 B，找出字典序最大的最长共同序列，输出其长度和元素。

数据范围约束：

• 测试数据组数 T 满足 $1 \le T \le 10^5$。
• 每个序列的长度 n 满足 $2 \le n \le 2 \cdot 10^5$。
• 所有测试数据的 n 之和不超过 $2 \cdot 10^5$。
• 序列中的元素都是 $1$ 到 $n$ 的整数且互不相同，每个整数恰好出现一次。

输入描述

第一行包含一个整数 $T$（$1 \le T \le 10^5$），表示测试数据的组数。 接下来每组数据描述如下：

• 第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$），表示序列的长度。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示第一个序列 $A$。
• 第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$，表示第二个序列 $B$。 保证单个测试文件中所有 $n$ 的总和不超过 $2 \cdot 10^5$，且每个序列中 $1$ 到 $n$ 每个整数恰好出现一次。

输出描述

对于每组测试数据，输出两行： 第一行输出一个整数 $k$，表示最长共同序列的长度。 第二行输出 $k$ 个整数，用空格分隔，表示字典序最大的那个最长共同序列。

样例1

输入

1
2
2 1
1 2

输出

1
2

说明

序列 $A = [2, 1]$，$B = [1, 2]$。两个序列的最长公共子序列长度只能是 1，因为任意长度为 2 的子序列都无法同时是两个序列的子序列（例如 $[2, 1]$ 在 $B$ 中不是子序列，$[1, 2]$ 在 $A$ 中不是子序列）。长度为 1 的公共子序列有 [1] 和 [2]，其中字典序更大的为 [2]，因此输出长度 1 和序列 2。$n = 2$ 是题目允许的最小长度，本样例验证了边界情况。

样例2

输入

1
4
1 2 3 4
1 3 2 4

输出

3
1 3 4

说明

$A = [1, 2, 3, 4]$，$B = [1, 3, 2, 4]$。最长公共子序列的长度为 3。长度 3 的公共子序列有两条：$[1, 2, 4]$ 和 $[1, 3, 4]$。在长度相同的前提下需要选择字典序最大的序列。比较第一个不同位置（第 2 个元素）：3 大于 2，因此 $[1, 3, 4]$ 的字典序更大。最终输出长度 3 以及序列 1 3 4。

样例3

输入

2
3
1 2 3
2 3 1
5
5 4 3 2 1
1 2 3 4 5

输出

2
2 3
1
5

说明

第一组数据：$A = [1, 2, 3]$，$B = [2, 3, 1]$。最长公共子序列为 $[2, 3]$，长度为 2，也是唯一长度为 2 的公共子序列，故答案长度为 2，序列为 2 3。

第二组数据：$A = [5, 4, 3, 2, 1]$，$B = [1, 2, 3, 4, 5]$。两个序列互为逆序，不存在长度大于 1 的公共子序列。所有长度为 1 的公共子序列中，最大数字为 5，因此输出长度 1，序列 5。这组数据展示了完全逆序的退化情况。