Непрефіксні коди#2928

Непрефіксні коди

2 секунди
256 мегабайтів
Легка

Розглянемо множину з символів \{1, 2, \ldots, n\}. Кожному символу відповідає вектор b_i, що складається з та . Будь-яка послідовність цих символів c = c_1c_2\ldots c_k визначає вектор з та , утворений шляхом конкатенації b_{c_1}, b_{c_2}, \ldots, b_{c_k}; позначимо його як . Знайдіть найкоротший вектор , що складається з та , такий, що X = B(c) і X = B(d) для двох різних впорядкованих послідовностей та . Якщо таких послідовностей декілька, виведіть лексикографічно найменшу. Гарантується, що принаймні одна така послідовність існує.

Вхідні дані

Перший рядок містить одне ціле число (2 \leq N \leq 20). Наступні рядків містять вектори b_i, кожен з яких має довжину не більше .

Вихідні дані

У першому рядку виведіть довжину знайденої послідовності. У другому рядку виведіть саму послідовність.

Приклади

Приклад 1

Loading
Loading