小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$$$ 非递减。