分数: 800 点
问题陈述
给你一个正整数 N 和长度的整数序列 N: A=(A_1,A_2,\ldots,A_N) 和 B=(B_1,B_2,\ldots,B_N).
你执行 N-1 操作 A。的 i第次操作 (1\le i\le N-1) 如下:
- 选择一个整数 j 满意 i < j \le N,并交换值 A_i 和 A_j.
查找最大可能的索引数 k (1\le k\le N) 满意 A_k=B_k 之后 N-1 操作。
你被给予 T 测试用例;解决它们中的每一个。
约束
- 1\le T\le 10^5
- 2\le N\le 3\times 10^5
- 1\le A_i,B_i\le N
- 总和 N 所有测试用例最多 3\times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T
每个测试用例均按以下格式给出:
N A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N
输出
按顺序输出测试用例的答案,以换行符分隔。
示例输入 1
3 3 1 1 2 1 2 3 5 1 2 3 4 5 5 4 3 2 1 6 1 2 1 1 2 1 1 1 1 2 2 2
示例输出 1
2 2 5
考虑第一个测试用例。
通过执行如下操作,索引的数量 k 满意 A_k=B_k 之后 N-1 可以进行操作 2.
- 当 i=1:选择 j=2. A=(1,1,2).
- 当 i=2:选择 j=3. A=(1,2,1).
索引数量 k 满意 A_k=B_k 之后 N-1 操作不能大于 2,所以输出 2 在第一行。