← 返回题目列表

Codeforces · 1311/B

B. 奇怪排序

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

给你一个长度为 $$$n$$$ 的数组 $$$a$$$。

您还会获得一组不同的位置 $$$p_1, p_2, \dots, p_m$$$,其中 $$$1 \le p_i < n$$$。位置 $$$p_i$$$ 意味着您可以交换元素 $$$a[p_i]$$$ 和 $$$a[p_i + 1]$$$。您可以对每个给定位置多次应用此操作。

您的任务是确定是否可以仅使用允许的交换以非降序($$$a_1 \le a_2 \le \dots \le a_n$$$)对初始数组进行排序。

例如,如果$$$a = [3, 2, 1]$$$并且$$$p = [1, 2]$$$,那么我们可以首先交换元素$$$a[2]$$$和$$$a[3]$$$(因为位置$$$2$$$包含在给定集合$$$p$$$中)。我们得到数组 $$$a = [3, 1, 2]$$$。然后我们交换$$$a[1]$$$和$$$a[2]$$$(位置$$$1$$$也包含在$$$p$$$中)。我们得到数组 $$$a = [1, 3, 2]$$$。最后,我们再次交换$$$a[2]$$$和$$$a[3]$$$,得到数组$$$a = [1, 2, 3]$$$,按非降序排序。

您可以看到,如果 $$$a = [4, 1, 2, 3]$$$ 且 $$$p = [3, 2]$$$ 则无法对数组进行排序。

您必须回答 $$$t$$$ 独立测试用例。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。

然后是 $$$t$$$ 测试用例。每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le m < n \le 100$$$) — $$$a$$$ 中的元素数量和 $$$p$$$ 中的元素数量。测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$)。测试用例的第三行包含 $$$m$$$ 整数 $$$p_1, p_2, \dots, p_m$$$ ($$$1 \le p_i < n$$$, 所有 $$$p_i$$$ 都是不同的) — 问题陈述中描述的位置集。

输出

对于每个测试用例,如果您可以仅使用允许的交换对初始数组进行非降序排序 ($$$a_1 \le a_2 \le \dots \le a_n$$$),则打印答案 —“YES”(不带引号)。否则,打印“NO”。

示例

输入 #1

6
3 2
3 2 1
1 2
4 2
4 1 2 3
3 2
5 1
1 2 3 4 5
1
4 2
2 1 4 3
1 3
4 2
4 3 2 1
1 3
5 2
2 1 2 3 3
1 4

输出 #1

YES
NO
YES
YES
NO
YES