29312번 - Палиндромы 스페셜 저지다국어

Василий после тяжёлого футбольного мятча любит отдыхать, а именно смотреть кино или играть в компьютерные игры. Но после очередного матча ему надоело играть в футбольные симуляторы и смотреть сериалы. Тогда он решил взять у своего брата-близнеца игру 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.