Equal Reversal

题意翻译

给定一个长度为 $n$ 的序列 $a$，有如下操作： - 选择两个整数 $l$ 与 $r$ 满足 $1 \le l \le r \le n$ 且 $a_l=a_r$，翻转区间 $[l,r]$，即将 $[a_l,a_{l+1},\dots,a_r]$ 改为 $[a_r,a_{r-1},\dots,a_l]$。 给定 $a$ 的一个排列 $b$，试着执行至多 $n^2$ 次上述操作将 $a$ 修改为 $b$，或者报告无解。 本题有多组数据，你需要在第一行读入 $t$ 代表数据组数。 本题数据保证：$1 \le t \le 100$，$1 \le \sum n \le 500$。 输出格式：若无解输出 `NO`。否则第一行输出 `YES`，接下来输出一个整数 $k$ 代表你使用的操作数，紧接着 $k$ 行每行包括两个数 $l_i$ 与 $r_i$ 来描述你执行的第 $i$ 个操作。 _Translated by Yakumo_Ran, who loves the problem very much._

题目描述

There is an array $ a $ of length $ n $ . You may perform the following operation on it: - Choose two indices $ l $ and $ r $ where $ 1 \le l \le r \le n $ and $ a_l = a_r $ . Then, reverse the subsegment from the $ l $ -th to the $ r $ -th element, i. e. set $ [a_l, a_{l + 1}, \ldots, a_{r - 1}, a_r] $ to $ [a_r, a_{r-1}, \ldots, a_{l+1}, a_l] $ . You are also given another array $ b $ of length $ n $ which is a permutation of $ a $ . Find a sequence of at most $ n^2 $ operations that transforms array $ a $ into $ b $ , or report that no such sequence exists.

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 100 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains an integer $ n $ ( $ 1 \le n \le 500 $ ) — the length of array $ a $ and $ b $ . The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le n $ ) — elements of the array $ a $ . The third line of each test case contains $ n $ integers $ b_1, b_2, \ldots, b_n $ ( $ 1 \le b_i \le n $ ) — elements of the array $ b $ . It is guaranteed that $ b $ is a permutation of $ a $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 500 $ .

输出格式

For each test case, output "NO" (without quotes) if it is impossible to turn $ a $ into $ b $ using at most $ n^2 $ operations. Otherwise, output "YES" (without quotes). Then output an integer $ k $ ( $ 0 \leq k \leq n^2 $ ) denoting the number of operations you will perform. Note that you don't have to minimize the number of operations. Afterwards, output $ k $ lines. The $ i $ -th line should contain two integers $ l_i $ and $ r_i $ ( $ 1 \leq l_i \leq r_i \leq n $ ) — the left and right indices for the $ i $ -th operation. You can output "YES" and "NO" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response). If there are multiple possible sequences of operations, you may output any of them.

输入输出样例

输入样例 #1

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

输出样例 #1

YES
2
5 8
1 6
YES
2
1 4
3 6
NO
NO
YES
0

说明

In the first test case, we can perform the following operations: $ $[1,2,4,3,1,2,1,1] \xrightarrow[l=5,\,r=8]{} [1,2,4,3,1,1,2,1] \xrightarrow[l=1,\,r=6]{} [1,1,3,4,2,1,2,1]. $ $ </p><p>In the second test case, we can perform the following operations: $ $ [1,2,3,1,3,2,3] \xrightarrow[l=1,\,r=4]{} [1,3,2,1,3,2,3] \xrightarrow[l=3,\,r=6]{} [1,3,2,3,1,2,3]. $ $ </p><p>It can be proven that it is impossible to turn $ a $ into $ b$ in the third and fourth test cases.

**题目大意**：

有一个长度为 $ n $ 的序列 $ a $，你可以进行以下操作：

- 选择两个整数 $ l $ 和 $ r $ 满足 $ 1 \le l \le r \le n $ 且 $ a_l = a_r $，然后翻转区间 $[l, r]$，即将 $[a_l, a_{l+1}, \ldots, a_r]$ 改为 $[a_r, a_{r-1}, \ldots, a_l]$。

给你另一个长度为 $ n $ 的序列 $ b $，它是 $ a $ 的一个排列。找到一系列至多 $ n^2 $ 次的操作，将序列 $ a $ 变为 $ b $，或者报告无解。

本题有多组数据，第一行输入 $ t $ 代表数据组数。保证：$ 1 \le t \le 100 $，$ 1 \le \sum n \le 500 $。

**输入输出数据格式**：

**输入格式**：
- 第一行包含一个整数 $ t $（$ 1 \leq t \leq 100 $）——测试用例的数量。
- 每个测试用例的第一行包含一个整数 $ n $（$ 1 \le n \le 500 $）——数组 $ a $ 和 $ b $ 的长度。
- 每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ 1 \le a_i \le n $）——数组 $ a $ 的元素。
- 每个测试用例的第三行包含 $ n $ 个整数 $ b_1, b_2, \ldots, b_n $（$ 1 \le b_i \le n $）——数组 $ b $ 的元素。
- 保证 $ b $ 是 $ a $ 的一个排列。
- 保证所有测试用例的 $ n $ 之和不超过 $ 500 $。

**输出格式**：
- 对于每个测试用例，如果无法使用至多 $ n^2 $ 次操作将 $ a $ 变为 $ b $，则输出 "NO"（不带引号）。
- 否则，输出 "YES"（不带引号）。然后输出一个整数 $ k $（$ 0 \leq k \leq n^2 $），表示你将执行的操作数。注意，你没有必要最小化操作数。
- 接着输出 $ k $ 行，第 $ i $ 行应包含两个整数 $ l_i $ 和 $ r_i $（$ 1 \leq l_i \leq r_i \leq n $）——第 $ i $ 个操作的左右索引。
- 你可以在任何情况下输出 "YES" 和 "NO"（例如，字符串 "yEs"、"yes" 和 "Yes" 将被视为肯定回答）。
- 如果存在多个可能的操作序列，你可以输出其中任何一个。**题目大意**： 有一个长度为 $ n $ 的序列 $ a $，你可以进行以下操作： - 选择两个整数 $ l $ 和 $ r $ 满足 $ 1 \le l \le r \le n $ 且 $ a_l = a_r $，然后翻转区间 $[l, r]$，即将 $[a_l, a_{l+1}, \ldots, a_r]$ 改为 $[a_r, a_{r-1}, \ldots, a_l]$。 给你另一个长度为 $ n $ 的序列 $ b $，它是 $ a $ 的一个排列。找到一系列至多 $ n^2 $ 次的操作，将序列 $ a $ 变为 $ b $，或者报告无解。 本题有多组数据，第一行输入 $ t $ 代表数据组数。保证：$ 1 \le t \le 100 $，$ 1 \le \sum n \le 500 $。 **输入输出数据格式**： **输入格式**： - 第一行包含一个整数 $ t $（$ 1 \leq t \leq 100 $）——测试用例的数量。 - 每个测试用例的第一行包含一个整数 $ n $（$ 1 \le n \le 500 $）——数组 $ a $ 和 $ b $ 的长度。 - 每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ 1 \le a_i \le n $）——数组 $ a $ 的元素。 - 每个测试用例的第三行包含 $ n $ 个整数 $ b_1, b_2, \ldots, b_n $（$ 1 \le b_i \le n $）——数组 $ b $ 的元素。 - 保证 $ b $ 是 $ a $ 的一个排列。 - 保证所有测试用例的 $ n $ 之和不超过 $ 500 $。 **输出格式**： - 对于每个测试用例，如果无法使用至多 $ n^2 $ 次操作将 $ a $ 变为 $ b $，则输出 "NO"（不带引号）。 - 否则，输出 "YES"（不带引号）。然后输出一个整数 $ k $（$ 0 \leq k \leq n^2 $），表示你将执行的操作数。注意，你没有必要最小化操作数。 - 接着输出 $ k $ 行，第 $ i $ 行应包含两个整数 $ l_i $ 和 $ r_i $（$ 1 \leq l_i \leq r_i \leq n $）——第 $ i $ 个操作的左右索引。 - 你可以在任何情况下输出 "YES" 和 "NO"（例如，字符串 "yEs"、"yes" 和 "Yes" 将被视为肯定回答）。 - 如果存在多个可能的操作序列，你可以输出其中任何一个。