Вам нужно напечатать \(N\) слов на Movable Type Printer. Movable Type Printers — это старые принтеры, для работы которых требуется ставить маленькие металлические кусочки (каждый из кусочков содержит одну букву) в определенном порядке, образуя таким образом слова. Потом все они вдавливаются в лист бумаги. Таким образом печатается одно слово. Ваш принтер позволяет делать следующие операции:

• Добавить букву в конец слова, находящегося сейчас на принтере.
• Удалить последнюю букву из слова, находящегося сейчас на принтере. Эту операцию можно делать, только если слово содержит хотя бы одну букву.
• Напечатать слово, находящееся на принтере (при этом слово никуда не исчезает, можно печатать его ещё раз и ещё раз).

Изначально на принтере содержится пустое слово. В конце печати на принтере можно оставить непустое слово. Слова, которые вам даны, вы можете печатать в произвольном порядке.

Каждая из трёх операций занимает одну единицу времени. Вам нужно найти последовательность операций, которая печатает данные \(N\) слов за минимальное время. Если минимальных последовательностaей несколько, выведите любую.

Строка s называется супрефиксом для строки t, если t начинается с s и заканчивается на s. Например, «abra» является супрефиксом для строки «abracadabra». В частности, сама строка t является своим супрефиксом. Супрефиксы играют важную роль в различных алгоритмах на строках.

В этой задаче требуется решить обратную задачу о поиске супрефикса, которая заключается в следующем. Задан словарь, содержащий n слов t₁, t₂, …, t_n и набор из m строк-образцов s₁, s₂, …, s_m. Необходимо для каждой строки-образца из заданного набора найти количество слов в словаре, для которых эта строка-образец является супрефиксом.

Требуется написать программу, которая по заданному числу n, n словам словаря t₁, t₂, …, t_n, заданному числу m и m строкам-образцам s₁, s₂, …, s_m вычислит для каждой строки-образца количество слов из словаря, для которых эта строка-образец является супрефиксом.

Вова и Марина любят играть в игры, а особенно — придумывать к ним свои правила. Недавно они открыли для себя веселую игру «Чапаев», в которой игроки должны сбивать щелчками шашки вражеского цвета с шахматной доски (также эта игра известна под названием «Щелкунчики»). Вдоволь наигравшись, они решили модифицировать правила, добавив игре математическую сложность.

Теперь они играют в «Чапаева» не на шахматной доске, а на доске в форме дерева! Их дерево состоит из \(N\) вершин. Вершина 1 является корнем дерева, а из каждой из оставшихся вершин проведено ребро в некоторую вершину с меньшим номером — ее непосредственного предка.

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

Игроки делают ходы по очереди. Проигрывает тот игрок, к ходу которого на доске не остается шашек.

Придуманная ими игра замечательна также тем, что на одной и той же доске можно играть, начиная с разных начальных позиций шашек. Практика показала, что самые интересные партии получаются, если исходно расставить фишки во все вершины, являющиеся потомками (непосредственными или косвенными) некоторой вершины Root, при этом в саму вершину Root фишка не ставится.

Дети решили сыграть \(N\) партий, перебрав в качестве вершины Root каждую вершину дерева по одному разу. Если у очередной вершины Root нет потомков, и на доске исходно не оказывается ни одной фишки, то игры не происходит, и дети переходят к следующей расстановке. В каждой партии Марина ходит первой.

Вова интересуется у вас, в скольких партиях Марина сможет одержать победу, если игроки будут действовать оптимально.

Комментарий

Разберем тест из условия. Доска для игры показана на рисунках ниже. Дети сыграют четыре партии, выбирая в качестве Root вершины 1, 2, 3 и 5. Если выбрать в качестве Root любую из трех оставшихся вершин, на доске исходно не окажется ни одной фишки, поэтому игры не произойдет.

Если выбрать в качестве Root вершину 5, фишки будут исходно находиться в вершинах 6 и 7. В такой партии Марина проигрывает: после того, как она сбивает любую из этих двух фишек с доски, Вова сбивает оставшуюся и заканчивает партию.

Если выбрать в качестве Root вершину 2 или 3, у Марины будет возможность выиграть игру за один ход, щелкнув по фишке из вершины 4 (при этом, в случае Root = 2, она по пути также собьет фишку из 3 вершины по правилам игры)

Можно убедиться, что если выбрать в качестве Root вершину 1, у Марины также будет выигрышная стратегия. Для этого первым ходом Марина должна сбить фишку из вершины 2. Пример партии с таким начальным расположением показан ниже.

Таким образом, Марина выигрывает в трех партиях

Известно, что в солнечной системе есть 8 планет и один планетоид. Мало кто знает, что ещё есть секретная планета, населенная медведями. Именно туда ассоциация Savez отправляет бравого генерала Хенрика для изучения медведей. Выяснилось, что медведи умеют телепортироваться. Расчётливый генерал Хедрик решил завербовать их в свою армию.

У одного медведя есть N строк (обозначим i -ю из них x _i ). Исследования показывают, что количество раз, которое может телепортироваться медведь равно длине наибольшей подпоследовательности этих строк, удовлетворяющей такому правилу: строки x _i и x _j ( i < j ) могут принадлежать одной такой последовательности, если x _i является и префиксом, и суффиксом x _j .

Помогите уставшему от долгого полёта генералу Хендрику определить, сколько телепортаций сможет сделать данный медведь.