print2061. Палиндромы

printПалиндромы

Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Василий после тяжёлого футбольного мятча любит отдыхать, а именно смотреть кино или играть в компьютерные игры. Но после очередного матча ему надоело играть в футбольные симуляторы и смотреть сериалы. Тогда он решил взять у своего брата-близнеца игру Palin.
Игра заключалась в следующем: дана строка `S` и `k` правил замены одного символа на другой. То есть, если `i`-й символ строки будет равен `a_j`, то его можно будет заменить на символ `b_j`, где `a_j` и `b_j` – символы `j`-го правила замены. Кроме того, если символ номер `i` в строке уже был изменен, то изменить его еще раз невозможно. Требуется из данной строки получить палиндром. Напомним, что палиндромом является строка, которая одинаково читается и слева направо, и справа налево.
И тут Василий задался следующим вопросом: за какое минимальное количество операций замены такое возможно?
В первой строке входного файла дана строка `S` (`0\ <\ |S|\ ≤\ 10^5`), содержащая только маленькие латинские буквы. Во второй строке дано число `k` (`0\ ≤\ k\ ≤\ 26`) – количество правил. Следующие `k` строк содержат по два символа `a_i` и `b_i` (маленькие латинские буквы) – символы в очередном правиле замены. Все `a_i` различны.
Если из данной строки можно получить палиндром, следуя описанным правилам, то в первой строке выходного файла выведите минимальное количество операций замены, выполнив которые это можно сделать. Во второй строке в таком случае выведите номера символов, которые необходимо изменить. Символы в строке нумеруются с единицы.
Если же получить из данной строки палиндром невозможно, выведите в первой строке выходного файла `-1`.

Пример ввода 1

abc
1
a c

Пример вывода 1

1
1           

Пример ввода 2

abc
1
b c

Пример вывода 2

-1
Источник: neerc.ifmo.ru/school
loading