codeforces#P1967D. Long Way to be Non-decreasing

    ID: 34613 远端评测题 4000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>binary searchdfs and similargraphsimplementationshortest pathstwo pointers

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]$.
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.