F. Ханаби
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Последний Агни Кай — Джереми Закерман, Аватар: Легенда об Аанге

Пусть $$$n, m$$$ — положительные целые числа. Айро и Зуко играют в вариант Ханаби, кооперативную карточную игру, с $$$n$$$ рангами ($$$1, \ldots, n$$$) и $$$m$$$ цветами ($$$1, \ldots, m$$$). В частности, Зуко держит в руке $$$n \cdot m$$$ карт, содержащих по одной карте для каждой возможной комбинации ранга и цвета. В свой ход он может выбрать любую из карт и сыграть её на стол. Однако, если он попытается сыграть карту ранга $$$r \geq 2$$$ и цвета $$$c$$$, когда карта ранга $$$r-1$$$ и цвета $$$c$$$ ещё не была сыграна, они проиграют.

Чтобы сделать эту задачу намного интереснее, Зуко будет держать все свои карты лицом к Айро, так что только Айро сможет видеть их ранги и цвета. Чтобы дать Зуко информацию, в свой ход Айро может дать ему следующие типы подсказок:

  • Подсказка по рангу для ранга $$$r$$$ выделит позиции всех оставшихся карт в его руке с рангом $$$r$$$.
  • Подсказка по цвету для цвета $$$c$$$ выделит позиции всех оставшихся карт в его руке с цветом $$$c$$$.

Подсказка может быть дана только в том случае, если она выделяет хотя бы одну карту. Также, перед тем как дать новую подсказку, все карты сбрасываются в невыделенное состояние.

Игра начинается с того, что Айро дает подсказку, затем Зуко играет карту, и они чередуются до тех пор, пока либо все карты не будут сыграны на стол, либо какая-то карта не будет сыграна в недопустимом порядке.

Зуко решил, что в свой ход он всегда будет играть самую левую выделенную карту в своей руке. Айро хотел бы сделать серию подсказок, которые как заставят Зуко играть карты в допустимом порядке, так и минимизируют количество ходов, на которых его подсказка изменилась с предыдущего хода.

Вычислите минимальное количество раз, когда подсказка Айро может измениться между ходами.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n, m \leq 2 \cdot 10^5, 1 \leq n \cdot m \leq 2 \cdot 10^5$$$) — количество рангов и цветов соответственно.

Вторая строка каждого набора содержит $$$n \cdot m$$$ целых чисел $$$r_1, r_2, \ldots, r_{n \cdot m}$$$ ($$$1 \leq r_i \leq n$$$), ранги карт в руке Зуко слева направо.

Третья строка каждого набора содержит $$$n \cdot m$$$ целых чисел $$$c_1, c_2, \ldots, c_{n \cdot m}$$$ ($$$1 \leq c_i \leq m$$$), цвета карт в руке Зуко слева направо.

Гарантируется, что каждая из карт $$$(r, c)$$$ для $$$1 \leq r \leq n$$$, $$$1 \leq c \leq m$$$ появляется ровно один раз в данной руке $$$(r_1, c_1), (r_2, c_2), \ldots, (r_{n \cdot m}, c_{n \cdot m})$$$.

Гарантируется, что сумма значений $$$n \cdot m$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора выведите одно целое число — минимальное количество раз, когда подсказка Айро может измениться между ходами. Можно показать, что всегда возможно сыграть все карты в допустимом порядке.

Пример
Входные данные
7
3 2
1 2 3 1 2 3
1 1 1 2 2 2
2 2
2 1 2 1
1 2 2 1
1 7
1 1 1 1 1 1 1
7 6 5 4 3 2 1
5 1
1 4 2 3 5
1 1 1 1 1
8 3
1 1 1 3 2 2 5 3 3 6 4 4 7 5 5 8 6 6 2 7 7 4 8 8
1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3
9 4
2 1 1 2 3 2 3 5 3 6 5 6 7 7 8 5 9 9 4 4 8 1 2 3 6 7 8 4 5 6 9 1 4 7 9 8
4 2 1 2 2 1 4 2 1 2 1 1 1 2 2 4 1 2 2 1 1 3 3 3 4 4 4 3 3 3 4 4 4 3 3 3
6 2
2 1 3 2 4 3 5 4 6 6 1 5
1 2 1 2 1 2 1 2 1 2 1 2
Выходные данные
1
1
0
3
6
8
4
Примечание

В первом наборе оптимальная последовательность ходов выглядит следующим образом:

  • Айро дает подсказку по цвету для цвета $$$1$$$.
  • В следующие три хода Зуко играет карты рангов $$$1, 2$$$ и $$$3$$$ цвета $$$1$$$ в этом порядке.
  • Айро дает подсказку по цвету для цвета $$$2$$$.
  • В следующие три хода Зуко играет карты рангов $$$1, 2$$$ и $$$3$$$ цвета $$$2$$$ в этом порядке.
Айро изменяет свою подсказку $$$1$$$ раз, что можно показать как минимально.

Во втором наборе оптимальная последовательность ходов выглядит следующим образом:

  • Айро дает подсказку по рангу для ранга $$$1$$$.
  • В следующие два хода Зуко играет карты ранга $$$1$$$ цветов $$$2$$$ и $$$1$$$ в этом порядке.
  • Айро дает подсказку по рангу для ранга $$$2$$$.
  • В следующие два хода Зуко играет карты ранга $$$2$$$ цветов $$$1$$$ и $$$2$$$ в этом порядке.
Айро изменяет свою подсказку $$$1$$$ раз, что, как можно показать, является минимумом.

В третьем наборе оптимальная последовательность ходов выглядит следующим образом:

  • Айро дает подсказку по рангу для ранга $$$1$$$.
  • В следующие семь ходов Зуко играет карты ранга $$$1$$$ цветов $$$7, 6, 5, 4, 3, 2, 1$$$ в этом порядке.
Айро изменяет свою подсказку $$$0$$$ раз.

В четвертом наборе оптимальная последовательность ходов выглядит следующим образом:

  • Айро дает подсказку по рангу для ранга $$$1$$$.
  • Зуко играет карту ранга $$$1$$$ цвета $$$1$$$.
  • Айро дает подсказку по рангу для ранга $$$2$$$.
  • Зуко играет карту ранга $$$2$$$ цвета $$$1$$$.
  • Айро дает подсказку по рангу для ранга $$$3$$$.
  • Зуко играет карту ранга $$$3$$$ цвета $$$1$$$.
  • Айро дает подсказку по цвету для цвета $$$1$$$.
  • Зуко играет карты рангов $$$4$$$ и $$$5$$$ цвета $$$1$$$ в этом порядке.
Айро изменяет свою подсказку $$$3$$$ раза, что, как можно показать, является минимумом.