← 返回题目列表

Codeforces · 2118/F

F. 轮班和交换

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

给定数组 $$$a$$$ 和 $$$b$$$,长度为 $$$n$$$ 和一个整数 $$$m$$$。

数组仅包含从 $$$1$$$ 到 $$$m$$$ 的整数,并且两个数组都包含从 $$$1$$$ 到 $$$m$$$ 的所有整数。

您可以对$$$a$$$重复执行以下任一操作:

  • 循环移位$$$^{\text{*}}$$$数组向左
  • 交换两个相邻元素,如果它们的差异至少为 $$$2$$$。

是否可以将第一个数组转换为第二个数组?

$$$^{\text{*}}$$$长度为 $$$n$$$ 的零索引数组 $$$p$$$ 的左循环移位是一个数组 $$$q$$$,使得 $$$q_i = p_{(i + 1) \bmod n}$$$ 对于所有 $$$0 \le i \lt n$$$。

输入

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

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le m \le n \le 5\cdot10^5$$$) - 数组的长度和 $$$a$$$ 中不同元素的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le m$$$) — 表示数组 $$$a$$$。

第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le m$$$) — 表示数组 $$$b$$$。

保证两个数组都包含从 $$$1$$$ 到 $$$m$$$ 的所有整数。

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

输出

对于每个测试用例,输出“是“如果可以将第一个数组转换为第二个数组并且”NO" 否则。您可以以任何大小写(大写或小写)输出答案。例如字符串 "是", "是的", "是“,和”是”将被视为积极响应。

示例

输入
复制

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

输出
复制

YES
NO
YES
NO
YES
YES
NO
NO

注意

在第一个测试用例中,您可以通过以下步骤将数组 $$$a$$$ 转换为数组 $$$b$$$:

  • [$$$1$$$, $$$2$$$, $$$3$$$] — 向左移动
  • [$$$2$$$, $$$3$$$, $$$1$$$] — 掉期指数 $$$2$$$ 和 $$$3$$$
  • [$$$2$$$, $$$1$$$, $$$3$$$] — 向左移动
  • [$$$1$$$, $$$3$$$, $$$2$$$] — 向左移动
  • [$$$3$$$, $$$2$$$, $$$1$$$]

在第二个测试用例中,可以证明通过给定的操作不可能将数组 $$$a$$$ 转换为数组 $$$b$$$ 。