| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 4 | 3 | 3 | 100.000% |
Василий после тяжёлого футбольного мятча любит отдыхать, а именно смотреть кино или играть в компьютерные игры. Но после очередного матча ему надоело играть в футбольные симуляторы и смотреть сериалы. Тогда он решил взять у своего брата-близнеца игру Palin.
Игра заключалась в следующем: дана строка $S$ и $k$ правил замены одного символа на другой. То есть, если $i$ -й символ строки будет равен $a_j,ドル то его можно будет заменить на символ $b_j,ドル где $a_j$ и $b_j$ --- символы $j$-го правила замены. Кроме того, если символ номер $i$ в строке уже был изменен, то изменить его еще раз невозможно. Требуется из данной строки получить палиндром. Напомним, что палиндромом является строка, которая одинаково читается и слева направо, и справа налево.
И тут Василий задался следующим вопросом: за какое минимальное количество операций замены такое возможно?
В первой строке входного файла дана строка $S$ (0ドル < |S| \le 10^5$), содержащая только маленькие латинские буквы. Во второй строке дано число $k$ (0ドル \le k \le 26$) --- количество правил. Следующие $k$ строк содержат по два символа $a_i$ и $b_i$ (маленькие латинские буквы) --- символы в очередном правиле замены. Все $a_i$ различны.
Если из данной строки можно получить палиндром, следуя описанным правилам, то в первой строке выходного файла выведите минимальное количество операций замены, выполнив которые это можно сделать. Во второй строке в таком случае выведите номера символов, которые необходимо изменить. Символы в строке нумеруются с единицы.
Если же получить из данной строки палиндром невозможно, выведите в первой строке выходного файла -1.
abc 1 a c
1 1
abc 1 b c
-1
abc 2 c d d a
-1