← 返回题目列表

Codeforces · 1698/F

F. 等反转

中文机器翻译题面 查看原题

有一个长度为$$$n$$$的数组$$$a$$$。您可以对其进行如下操作:

- 选择两个索引 $$$l$$$ 和 $$$r$$$,其中 $$$1 \le l \le r \le n$$$ 和 $$$a_l = a_r$$$。然后,将子段从第 $$$l$$$ 反转到第 $$$r$$$ 元素,i。 e.将 $$$[a_l, a_{l + 1}, \ldots, a_{r - 1}, a_r]$$$ 设置为 $$$[a_r, a_{r-1}, \ldots, a_{l+1}, a_l]$$$。

您还获得了另一个长度为 $$$n$$$ 的数组 $$$b$$$,它是 $$$a$$$ 的排列。找到一个最多包含 $$$n^2$$$ 操作的序列,将数组 $$$a$$$ 转换为 $$$b$$$,或者报告不存在这样的序列。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$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”将被识别为肯定响应)。

如果有多个可能的操作序列,则可以输出其中任何一个。

示例

输入 #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

注意

在第一个测试用例中,我们可以执行以下操作: $$$$$$[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].$$$$$$

在第二个测试用例中,我们可以执行以下操作: $$$$$$[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].$$$$$$

可以证明,在第三个和第四个测试用例中,不可能将$$$a$$$变成$$$b$$$。