Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

D. Длинный путь к неубыванию
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Малышка R — волшебница, которая любит неубывающие массивы. У нее есть массив длины $$$n$$$, изначально равный $$$a_1, \ldots, a_n$$$, в котором каждый элемент — целое число в диапазоне $$$[1, m]$$$. Она хочет, чтобы он стал неубывающим, то есть выполнялось $$$a_1 \leq a_2 \leq \ldots \leq a_n$$$.

Для этого она может проделать несколько фокусов. У малышки R есть фиксированный массив $$$b_1\ldots b_m$$$ длины $$$m$$$. Формально определим фокус как процедуру, которая выполняет следующие действия по порядку:

  • Выбрать множество $$$S \subseteq \{1, 2, \ldots, n\}$$$.
  • Для каждого $$$u \in S$$$ присвоить $$$a_u$$$ значение $$$b_{a_u}$$$.

Малышка R задается вопросом, сколько нужно сделать фокусов, чтобы исходный массив стал неубывающим. Если это невозможно ни при каком количестве фокусов, выведите вместо этого $$$-1$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1\le t\le 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$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число: минимально необходимое количество фокусов или $$$-1$$$, если невозможно сделать $$$a_1, \ldots, a_n$$$ неубывающим.

Пример
Входные данные
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, \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$$$ неубывающим.