兵蚁排序

题目信息

时间限制: 1s

空间限制: 256M

输入文件: sort.in

输出文件: sort.out

题目描述

蚁后 Q 的蚁群正筹划着一场盛大的阅兵仪式，蚁后 Q 把蚁群中的兵蚁们分成若干纵队，设某个兵蚁纵队现在有 $n$ 只兵蚁，兵蚁们排成一个序列 $a$，第 $i$ 只兵蚁的战斗力为 $a_i$。蚁后 Q 的兵蚁们都接受过蚁后 Q 的训练，这使得兵蚁们能听懂蚁后 Q 的指挥：

• 选择一个区间 $[l, r]$，区间内的兵蚁们将按照战斗力从低到高排序，即设排序后的兵蚁序列为 $a'$，那么将有 $a'_l\leq a'_{l+1}\leq \dots \leq a'_r$

蚁后 Q 希望把此纵队的兵蚁们按照战斗力排成序列 $b$，因为这样能最好地展现蚁后 Q 蚁群的实力。

输入格式

第一行一个正整数 $T$，表示蚁后 Q 将兵蚁们分成了 $T$ 个兵蚁纵队

接下来对于每个纵队：

• 第一行一个正整数 $n$，表示纵队中兵蚁的数量
• 第二行 $n$ 个正整数 $a[1\dots n]$，表示该纵队中兵蚁当前的排序
• 第三行 $n$ 个正整数 $b[1\dots n]$，表示以后 Q 期望该纵队兵蚁最终的排序

输出格式

对于每个兵蚁纵队，首先输出一行 0/-1

• 若蚁后 Q 无法指挥兵蚁们按战斗力最终排序为 $b$，则输出 -1
• 若蚁后 Q 可以指挥兵蚁们按战斗力最终排序为 $b$，则输出 0

若第一行输出为 0，第二行输出一个整数 $m$ 表示蚁后 Q 需要指挥的次数，接下来 $m$ 行每行两个正整数 $l, r$，表示蚁后 Q 指挥的区间为 $[l, r]$，注意一个合法的指挥方案需要满足以下条件：

• $m\leq n^2$
• 每次指挥都要保证 $1\leq l\leq r\leq n$
• 指挥结束后，$a, b$ 相等

若存在多个合法的指挥方案，输出任意一个即可。

样例

样例输入 1

4
7
1 7 1 4 4 5 6
1 1 4 4 5 7 6
5
1 3 1 5 3
1 1 3 3 5
2
2 1
1 2
3
1 2 3
2 1 3

样例输出 1

0
1
2 6
0
2
2 3
4 5
0
1
1 2
-1

样例输入 2

7
8
2 3 4 5 6 5 1 4
1 2 3 4 5 6 5 4
7
1 7 4 3 2 5 6
1 5 2 3 4 7 6
7
4 6 5 1 2 7 3
4 3 1 2 5 6 7
7
4 6 7 5 2 3 1
1 3 4 2 6 5 7
7
6 4 1 5 3 2 7
1 5 2 4 6 3 7
7
6 4 7 3 1 2 5
4 6 1 5 2 3 7
7
6 5 7 4 3 1 2
6 5 4 2 3 1 7

样例输出 2

0
6
6 7
5 6
4 5
3 4
2 3
1 2
-1
-1
-1
-1
-1
-1

数据范围与提示

对于 $100 \%$ 的数据，$T \leq 10, \sum n \leq 1000,1 \leq a[i], b[i] \leq n$，保证 $a, b$ 中所有数字出现次数相同

子任务1 (20分)，$\sum n \leq 10$

子任务2 (20分)，$\sum n \leq 50$

子任务3 (30分)，$\sum n \leq 100$

子任务4 (30分)，$\sum n \leq 1000$

注意你需要保证输出方案中 $m \leq n^2$