#P1967D. Long Way to be Non-decreasing
Long Way to be Non-decreasing
Description
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.
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$.
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.
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.
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
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]$.
In the second case, it is impossible to make $a_1, \ldots, a_n$ non-decreasing.