Long Way to be Non-decreasing
Contest: Codeforces Round 942 (Div. 1)
Difficulty rating: 2800
Tags: binary search, dfs and similar, graphs, implementation, shortest paths, two pointers

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 format:
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 format:
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.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

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.

Example input:
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

Example output:
3
-1
3

Editorial:
If we separately consider each operation, it could be really hard.
Thus, binary search on the answer of magics. Greedily, we want $$$a_1$$$ as small as possible, and then $$$a_2$$$, etc.
Enumerate $$$i$$$ from $$$1$$$ to $$$n$$$. Enumerate $$$a_i = w$$$ for $$$w$$$ from $$$1$$$ to $$$m$$$. If it is possible for $$$a_i = w$$$ after $$$k$$$ steps, $$$i \gets i + 1$$$; Otherwise, $$$w \gets w + 1$$$. If $$$i$$$ gets to $$$n + 1$$$ first, it's valid. If $$$w$$$ gets to $$$m + 1$$$ first, it's invalid.
The last question is how to judge whether vertex $$$u$$$ is reachable from vertex $$$v$$$ in $$$k$$$ steps in $$$\mathcal O(1)$$$ time.
Build a graph with edges $$$i \to p_i$$$. Assume that the graph is a tree, now the condition is equivalent to
• $$$dep_u - dep_v \leq k$$$;
• $$$u$$$ is in the subtree of $$$v$$$. We can simply check the DFS order and size: $$$dfn_v < dfn_u < dfn_v + sz_v$$$.
However, the graph contains $$$n$$$ vertices and $$$n$$$ edges, so it turns out to be a pseudo forest. One of the processing ways is to cut one edge on the cycle of each pseudo tree. If the path from $$$u$$$ to $$$v$$$ doesn't contain the edge, we process the above method. Otherwise, let the cut edge be $$$s \Rightarrow t$$$ (In fact, $$$s$$$ is exactly the root of the tree), and we want $$$u \to s \Rightarrow t \to v$$$, so
• $$$dep_s - dep_u + dep_v - dep_t + 1 \leq k$$$;
• $$$u$$$ is in the subtree of $$$s$$$, while $$$t$$$ is in the subtree of $$$v$$$.
It takes a little time to implement, but be patient and clear-minded, and you are sure to get Accepted.