CF1967D.Long Way to be 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$。形式化地说，一次魔法操作定义如下：

• 选择一个集合 $S \subseteq \{1, 2, \ldots, n\}$。
• 对于每个 $u \in S$，将 $a_u$ 赋值为 $b_{a_u}$。

小 R 想知道，至少需要多少次魔法操作才能使初始数组变为非递减。如果无论进行多少次操作都无法实现，输出 $-1$。

每组测试数据包含多组测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 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$。

在第一个样例中，初始数组 $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$ 变为非递减。

由 ChatGPT 4.1 翻译