← 返回题目列表

Codeforces · 1967/D

D. 距离不减还有很长的路要走

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

小R是一个喜欢非减数组的魔术师。她有一个长度为 $$$n$$$ 的数组,最初为 $$$a_1, \ldots, a_n$$$,其中每个元素都是 $$$[1, m]$$$ 之间的整数。她希望它是非递减的,即 $$$a_1 \leq a_2 \leq \ldots \leq a_n$$$。

为此,她可以表演几种魔术。小R有一个固定数组$$$b_1\ldots b_m$$$,长度为$$$m$$$。正式地,让我们将技巧定义为按顺序执行以下操作的过程:

- 选择一个集合 $$$S \subseteq \{1, 2, \ldots, n\}$$$。
- 对于 S$$$ 中的每个 $$$u \,将 $$$a_u$$$ 分配给 $$$b_{a_u}$$$。

小R想知道至少需要多少技巧才能使初始数组不减。如果使用任何技巧都无法实现,请改为打印 $$$-1$$$。

输入

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

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1\leq n \leq 10^6$$$, $$$1 \leq m \leq 10^6$$$) - 初始数组的长度和数组中元素的范围。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, \ldots, a_n$$$ ($$$1 \leq a_i \leq m$$$) - 初始数组。

每个测试用例的第三行包含 $$$m$$$ 整数 $$$b_1, \ldots, b_m$$$ ($$$1 \leq b_i \leq m$$$) - 固定魔法数组。

保证所有测试用例的$$$n$$$总和不超过$$$10^6$$$,并且所有测试用例的$$$m$$$总和不超过$$$10^6$$$。

输出

对于每个测试用例,输出一个整数:所需的最小技巧数,或者如果不可能使 $$$a_1, \ldots, a_n$$$ 非递减,则输出 $$$-1$$$。

示例

输入 #1

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

输出 #1

3
-1
3

注意

在第一种情况下,初始数组 $$$a_1, \ldots, a_n$$$ 是 $$$[1, 6, 3, 7, 1]$$$。您可以选择$$$S$$$,如下所示:

- 第一招:$$$S = [2, 4, 5]$$$, $$$a = [1, 1, 3, 5, 2]$$$;
- 第二招:$$$S = [5]$$$, $$$a = [1, 1, 3, 5, 3]$$$;
- 第三招:$$$S = [5]$$$, $$$a = [1, 1, 3, 5, 5]$$$。

在第二种情况下,不可能使 $$$a_1, \ldots, a_n$$$ 非递减。