D.漫长的非递减之路 (Long Way to be Non-decreasing)

时间限制：$4$ 秒
内存限制：$512$ 兆字节

小 R 是一名喜欢非递减数组的魔法师。 她有一个长度为 $n$ 的初始数组 $a_1,a_2,\dots,a_n$，数组中每个元素都在区间 $[1,m]$ 内。 她希望把数组变成非递减序列，即满足：

为了达成目标，她可以施展若干次魔法操作。 小 R 拥有一个固定长度为 $m$ 的数组 $b_1,b_2,\dots,b_m$。

形式化定义一次魔法操作流程：

1. 选取下标集合 $S \subseteq \{1,2,\dots,n\}$；
2. 对每个 $u\in S$，令 $a_u \leftarrow b_{a_u}$。

求至少需要施展多少次魔法，才能把初始数组变成非递减数组。 若无论多少次操作都无法实现，输出 $-1$。

输入格式

多组测试用例。 第一行一个整数 $t$（$1\le t\le 10^4$），表示测试用例组数。

每组测试用例：

1. 第一行两个整数 $n,m$（$1\le n\le 10^6,\ 1\le m\le 10^6$），分别为数组长度、元素取值上界；
2. 第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1\le a_i\le m$），为初始数组；
3. 第三行 $m$ 个整数 $b_1,b_2,\dots,b_m$（$1\le b_i\le m$），为魔法固定数组。

保证所有测试用例的 $\boldsymbol{\sum n \le 10^6}$，且 $\boldsymbol{\sum m \le 10^6}$。

输出格式

对每组测试用例，输出一个整数：

• 最少需要的魔法次数；
• 无法实现则输出 $-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,6,3,7,1]$。

三次魔法选择集合如下：

1. 第一次魔法：选 $S=\{2,4,5\}$，数组变为 $[1,1,3,5,2]$；
2. 第二次魔法：选 $S=\{5\}$，数组变为 $[1,1,3,5,3]$；
3. 第三次魔法：选 $S=\{5\}$，数组变为 $[1,1,3,5,5]$。

最终得到非递减数组，最少需要 $3$ 次操作，且无法更少。

第二组数据：无论多少次魔法，都无法得到非递减数组，输出 $-1$。