← 返回题目列表

Codeforces · 2060/G

G. 有缺陷的排序

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

今天,Alice 给了 Bob 数组,让他再次按升序排序!到现在为止,没有人知道她已经这样做了多少次了。

给 Bob 两个序列 $$$a$$$ 和 $$$b$$$,长度均为 $$$n$$$。从 $$$1$$$ 到 $$$2n$$$ 范围内的所有整数在 $$$a$$$ 或 $$$b$$$ 中只出现一次。换句话说,连接的$$$^{\text{*}}$$$序列$$$a+b$$$是长度为$$$2n$$$的排列$$$^{\text{†}}$$$。

Bob 必须使用 Alice 的交换函数同时对两个序列进行升序排序。 Alice的交换函数实现如下:

- 给定两个索引 $$$i$$$ 和 $$$j$$$ ($$$i \neq j$$$),它将 $$$a_i$$$ 与 $$$b_j$$$ 交换,并将 $$$b_i$$$ 与 $$$a_j$$$ 交换。

给定序列 $$$a$$$ 和 $$$b$$$,请确定在使用 Alice 的交换函数任意次后,两个序列是否可以同时按升序排序。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$)。

每个测试用例的第二行包含 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 2n$$$)。

每个测试用例的第三行包含 $$$b_1,b_2,\ldots,b_n$$$ ($$$1 \le b_i \le 2n$$$)。

保证 $$$[1,2n]$$$ 范围内的所有整数在 $$$a$$$ 或 $$$b$$$ 中恰好出现一次。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

如果可以同时对两个序列进行排序,请在新行上打印“YES”。否则,在新行上打印“NO”。

任何情况下都可以输出答案。例如,字符串“yEs”、“yes”和“Yes”也将被识别为肯定响应。

示例

输入 #1

5
3
2 1 3
4 6 5
3
2 1 5
4 3 6
4
1 6 4 3
5 2 8 7
4
5 3 7 1
8 6 4 2
7
5 1 9 12 3 13 7
2 4 11 14 6 10 8

输出 #1

NO
YES
NO
YES
YES

注意

在第一个测试用例中,可以证明这是不可能的。

在第二个测试用例中,Bob 可以使用索引 $$$i=1$$$ 和 $$$j=2$$$ 执行一项操作。数组分别变为 $$$[3,4,5]$$$ 和 $$$[1,2,6]$$$。现在两个数组都已排序。