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

Хакеры опять пытаются составить забавные фразы, используя вывод нейросетей. В этот раз им очень захотелось получить массив строк $$$a$$$ длины $$$n$$$.

Исходно у них есть массив $$$c$$$ длины $$$n$$$, заполненный пропусками, которые обозначаются символом $$$*$$$. Таким образом, если $$$n=4$$$, то исходно $$$c=[*,*,*,*]$$$.

У хакеров есть доступ к $$$m$$$ нейросетям, у каждой из которых есть свой вариант ответа на их запрос – массив строк $$$b_i$$$ длины $$$n$$$.

Хакеры пытаются получить массив $$$a$$$ из массива $$$c$$$, используя следующие операции:

  1. Выбрать нейросеть $$$i$$$, которая проведёт следующую операцию над массивом $$$c$$$: выберет случайный пропуск, например, на позиции $$$j$$$, и заменит $$$c_j$$$ на $$$b_{i, j}$$$.

    Например, если была выбрана первая нейросеть и $$$c = [*, \text{«like»}, *]$$$, а $$$b_1 = [\text{«I»}, \text{«love»}, \text{«apples»}]$$$, то после операции с первой нейросетью $$$c$$$ может стать равным или $$$[\text{«I»}, \text{«like»}, *]$$$, или $$$[*, \text{«like»}, \text{«apples»}]$$$.

  2. Выбрать позицию $$$j$$$ и заменить $$$c_j$$$ на пропуск.

К сожалению, из-за особенностей хакерского доступа к нейросетям, хакеры смогут увидеть изменённый массив $$$c$$$ только после завершения всех операций, поэтому им придётся заранее задать всю последовательность операций.

Однако, случайное поведение нейросетей может привести к тому, что нужный массив так и не будет получен, или его получение потребует чрезмерного количества операций, поэтому хакеры рассчитывают на вашу помощь в выборе последовательности операций, которая гарантированно и за минимальное количество операций получит массив $$$a$$$.

Более формально, если существует последовательность операций, с помощью которой можно гарантированно получить массив $$$a$$$ из массива $$$c$$$, то среди всех таких последовательностей найдите ту, в которой минимальное количество операций, и выведите количество операций в ней.

Если последовательности операций, переводящей массив $$$c$$$ в массив $$$a$$$, не существует, то выведите $$$-1$$$.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n, m \le 500$$$) — длину исходного массива $$$a$$$ и количество нейросетей соответственно.

Вторая строка каждого набора входных данных содержит массив $$$a$$$, состоящий из $$$n$$$ строк $$$a_i$$$ ($$$1 \le |a_i| \le 10$$$), разделённых пробелами.

Следующие $$$m$$$ строк каждого набора входных данных содержат массивы $$$b_i$$$ — по одному в каждой строке, состоящие из $$$n$$$ строк $$$b_{i, j}$$$ ($$$1 \le |b_{i,j}| \le 10$$$), разделённых пробелами.

Гарантируется, что сумма $$$|a_i|$$$ и $$$|b_{i, j}|$$$ по всем тестовым наборам не превышает $$$2 \cdot 10^5$$$, а также что сумма $$$n \cdot m$$$ по всем тестовым наборам также не превышает $$$2 \cdot 10^5$$$.

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

Обратите внимание, что длина каждой отдельной строки из ввода не превышает $$$10$$$.

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

Выведите $$$t$$$ чисел — по одному числу на каждый набор входных данных, каждое в отдельной строке.

Если существует последовательность операций, позволяющих гарантированно получить массив $$$a$$$ из $$$i$$$-го набора данных, то $$$i$$$-е число — количество операций в минимальной такой последовательности.

Иначе в качестве $$$i$$$-го числа выведите $$$-1$$$.

Пример
Входные данные
4
3 3
I love apples
He likes apples
I love cats
They love dogs
3 2
Icy wake up
wake Icy up
wake up Icy
4 3
c o D E
c o D s
c O l S
c o m E
4 5
a s k A
d s D t
O R i A
a X b Y
b a k A
u s k J
Выходные данные
5
-1
6
8