У Поликарпа есть $$$n$$$ различных бинарных слов. Слово называется бинарным, если состоит только из символов '0' и '1'. Например, следующие слова являются бинарными: «0001», «11», «0» и «0011100».

Поликарп хочет предложить этот набор из $$$n$$$ слов для игры в слова. Напомним, что это такая игра, во время которой игроки называют слова и каждое очередное слово (начиная со второго названного) начинается на тот же символ, что закончилось предыдущее слово. Первое названное слово может быть любым. Например, следующая последовательность слов может быть произнесена во время игры: «0101», «1», «10», «00», «00001».

Переворотом строки называется операция изменения порядка символов строки на обратный. Например, строка «0111» после переворота примет вид: «1110», а строка «11010» после переворота примет вид: «01011».

Возможно, набор слов Поликарпа такой, что не существует способа расположить их все в таком порядке, который согласуется с правилами игры. По этой причине Поликарп хочет перевернуть некоторые строки из заданного набора так, чтобы:

• получившийся набор из $$$n$$$ строк всё еще содержал различные строки;
• строки из получившегося набора можно расположить в таком порядке, чтобы полученная последовательность из $$$n$$$ строк была согласована с правилами игры.

Помогите Поликарпу выбрать минимальный набор строк, которые надо перевернуть.