311297: CF1967D. Long Way to be Non-decreasing

D. Long Way to be Non-decreasingtime limit per test4 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

Little R is a magician who likes non-decreasing arrays. She has an array of length $n$, initially as $a_1, \ldots, a_n$, in which each element is an integer between $[1, m]$. She wants it to be non-decreasing, i.e., $a_1 \leq a_2 \leq \ldots \leq a_n$.

To do this, she can perform several magic tricks. Little R has a fixed array $b_1\ldots b_m$ of length $m$. Formally, let's define a trick as a procedure that does the following things in order:

• Choose a set $S \subseteq \{1, 2, \ldots, n\}$.
• For each $u \in S$, assign $a_u$ with $b_{a_u}$.

Little R wonders how many tricks are needed at least to make the initial array non-decreasing. If it is not possible with any amount of tricks, print $-1$ instead.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le 10^4$). The description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ($1\leq n \leq 10^6$, $1 \leq m \leq 10^6$) — the length of the initial array and the range of the elements in the array.

The second line of each test case contains $n$ integers $a_1, \ldots, a_n$ ($1 \leq a_i \leq m$) — the initial array.

The third line of each test case contains $m$ integers $b_1, \ldots, b_m$ ($1 \leq b_i \leq m$) — the fixed magic array.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$ and the sum of $m$ over all test cases does not exceed $10^6$.

Output

For each test case, output a single integer: the minimum number of tricks needed, or $-1$ if it is impossible to make $a_1, \ldots, a_n$ non-decreasing.

ExampleInput

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

Output

3
-1
3

Note

In the first case, the initial array $a_1, \ldots, a_n$ is $[1, 6, 3, 7, 1]$. You can choose $S$ as follows:

• first trick: $S = [2, 4, 5]$, $a = [1, 1, 3, 5, 2]$;
• second trick: $S = [5]$, $a = [1, 1, 3, 5, 3]$;
• third trick: $S = [5]$, $a = [1, 1, 3, 5, 5]$.

So it is possible to make $a_1, \ldots, a_n$ non-decreasing using $3$ tricks. It can be shown that this is the minimum possible amount of tricks.

In the second case, it is impossible to make $a_1, \ldots, a_n$ non-decreasing.

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

为了做到这一点，她可以执行几个魔术。小R有一个固定长度为m的数组b_1\ldots b_m。形式上，我们定义一个魔术为执行以下步骤的过程：

1. 选择一个集合S \subseteq \{1, 2, \ldots, n\}。
2. 对于每个u \in S，将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。

示例输入输出：
输入：
```
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
```
输出：
```
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]。
所以可以使用3个魔术使a_1, \ldots, a_n非递减。可以证明这是可能的最小魔术数量。
在第二个测试用例中，无法使a_1, \ldots, a_n非递减。题目大意： 小R是一位喜欢非递减数组的魔术师。她有一个长度为n的数组，最初为a_1, \ldots, a_n，其中每个元素都是一个位于[1, m]之间的整数。她希望这个数组是非递减的，即a_1 \leq a_2 \leq \ldots \leq a_n。 为了做到这一点，她可以执行几个魔术。小R有一个固定长度为m的数组b_1\ldots b_m。形式上，我们定义一个魔术为执行以下步骤的过程： 1. 选择一个集合S \subseteq \{1, 2, \ldots, n\}。 2. 对于每个u \in S，将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。 示例输入输出： 输入： ``` 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 ``` 输出： ``` 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]。 所以可以使用3个魔术使a_1, \ldots, a_n非递减。可以证明这是可能的最小魔术数量。 在第二个测试用例中，无法使a_1, \ldots, a_n非递减。