Недавно были выпущены колоды игральных карт нового формата. Значение каждой карты в колоде задается base64-строкой длины $$$k$$$. В рамках данной задачи под base64-строкой подразумевается строка, каждый символ которой может принимать одно из следующих $$$64$$$ значений: '#', '$', '0'–'9', 'A'–'Z' и 'a'–'z'.
Каждая колода состоит из $$$n = 64^k$$$ карт и содержит ровно по одной карте с каждым возможным значением. Более того, в запечатанной новой колоде карты расположены в порядке лексикографического возрастания их значений. Напомним, что строка $$$s$$$ лексикографически больше строки $$$t$$$ тогда и только тогда, когда для некоторого $$$i$$$ верно, что $$$s_1 = t_1$$$, ..., $$$s_{i - 1} = t_{i - 1}$$$, а $$$s_i > t_i$$$. Иными словами, когда после их общего (возможно, пустого) префикса в $$$s$$$ идет больший символ, чем в $$$t$$$.
Фокусник Чоно Урёку перемешивает колоду, бесконечное количество раз повторяя следующее действие:
Чоно собирается показать $$$m$$$ фокусов. Чтобы $$$i$$$-й фокус удался, ему необходимо, чтобы карта со значением $$$x_i$$$ оказалась на позиции, на которой в изначальной (запечатанной) колоде находилась карта со значением $$$y_i$$$. Считая, что для каждого фокуса Чоно берет новую запечатанную колоду, помогите ему определить, какое минимальное число перемешиваний понадобится для каждого фокуса.
В первой строке ввода через пробел даны два целых числа $$$k$$$ и $$$m$$$ — длина значения каждой карты и количество фокусов ($$$1 \leqslant k \leqslant 2500$$$; $$$1 \leqslant m \leqslant 1000$$$).
В следующих $$$m$$$ строках перечислены описания фокусов. В $$$i$$$-й их них через пробел даны две строки $$$x_i$$$ и $$$y_i$$$ — значения карт, фигурирующих в $$$i$$$-м фокусе ($$$|x_i| = |y_i| = k$$$). Гарантируется, что $$$x_i$$$ и $$$y_i$$$ состоят только из указанных в условии символов.
Для каждого фокуса выведите в отдельной строке номер перемешивания, после которого карта со значением $$$x_i$$$ впервые окажется на позиции $$$y_i$$$.
Если карта изначально находится на нужной позиции, выведите $$$0$$$. Если же такое событие никогда не произойдет, выведите $$$-1$$$.
Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач, а также тесты из условия успешно пройдены.
Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
1 | 8 | $$$k = 1$$$, $$$m \leqslant 200$$$ | – | полная |
2 | 11 | $$$k \leqslant 10$$$, все $$$x_i$$$ равны между собой | – | полная |
3 | 13 | $$$k \leqslant 2$$$ | 1 | полная |
4 | 12 | $$$k \leqslant 50$$$, $$$m \leqslant 200$$$ | – | полная |
5 | 18 | $$$k, m \leqslant 300$$$ | 4 | полная |
6 | 19 | $$$k = 1024$$$, $$$m \leqslant 700$$$ | – | первая ошибка |
7 | 19 | нет | 1 – 6 | первая ошибка |
1 7 # # U $ 4 3 t D D t 2 $ $ 2
0 1 -1 3 3 4 2
3 8 Hd7 CYZ mZ$ 1Z8 iYq poa JlP edh SyR uxw aCp n5O I#g Oq8 wrP tir
2 13 15 -1 13 17 -1 1
ASCII коды используемых в значениях карт символов принимают значения $$$35$$$ ('#'), $$$36$$$ ('$'), от $$$48$$$ до $$$57$$$ (цифры), от $$$65$$$ до $$$90$$$ (заглавные латинские буквы) и от $$$97$$$ до $$$122$$$ (строчные латинские буквы).