← 返回题目列表

Codeforces · 1983/D

D. 交换困境

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

给定两个不同正整数数组 $$$a$$$ 和 $$$b$$$,长度为 $$$n$$$,我们希望使这两个数组相同。当对于所有 $$$1 \le i \le k$$$、$$$x_i = y_i$$$ 时,两个长度为 $$$k$$$ 的数组 $$$x$$$ 和 $$$y$$$ 被认为是相同的。

现在一步一步,你可以在 $$$a$$$ ($$$l \le r$$$) 中选择一些索引 $$$l$$$ 和 $$$r$$$ 并交换 $$$a_l$$$ 和 $$$a_r$$$,然后在 $$$b$$$ 中选择一些 $$$p$$$ 和 $$$q$$$ ($$$p \le q$$$) 这样$$$r-l=q-p$$$ 并交换 $$$b_p$$$ 和 $$$b_q$$$。

是否可以使两个数组相同?

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 数组 $$$a$$$ 和 $$$b$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 不同的整数 $$$a_1,a_2,a_3,\ldots,a_n$$$ ($$$1 \le a_i \le 2 \cdot 10^5$$$) - 数组 $$$a$$$ 中的整数。

每个测试用例的第三行包含 $$$n$$$ 不同的整数 $$$b_1,b_2,b_3,\ldots,b_n$$$ ($$$1 \le b_i \le 2 \cdot 10^5$$$) — 数组 $$$b$$$ 中的整数。

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

输出

对于每个测试用例,如果数组 $$$a$$$ 和 $$$b$$$ 可以相同,则打印“YES”。否则,打印“NO”。可以输出任何情况(上限或下限)的答案。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应。

示例

输入 #1

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

输出 #1

YES
NO
YES
NO
NO
NO

注意

在第一个测试用例中,您不需要执行任何操作,因为数组是相同的。

在第二个测试用例中,可以证明没有办法使数组相同。

在第三个测试用例中,使数组相同的方法之一是首先选择 $$$l=1$$$、$$$r=3$$$、$$$p=1$$$、$$$q=3$$$,然后选择 $$$l=1$$$、$$$r=2$$$、$$$p=3$$$、$$$q=4$$$。