Вам даны \(n\) строк \(s_1, s_2, \ldots, s_n\), состоящих из строчных и заглавных латинских букв. Более того, каждый символ в каждой строке встречается не более двух раз. Найдите самую длинную общую подпоследовательность этих строк.
Строка \(t\) является подпоследовательностью строки \(s\), если \(t\) может быть получена из \(s\) удалением нескольких (возможно, ни одного или всех) символов.
Выходные данные
Для каждого набора входных данных выведите ответ в двух строках.
В первой строке выведите длину самой длинной общей подпоследовательности.
Во второй — саму подпоследовательность. Если существует несколько самых длинных общих подпоследовательностей, выведите любую из них.
Примечание
В первом наборе входных данных одна из самых длинных общих подпоследовательностей это «A». Нет ни одной общей подпоследовательности длины \(2\).
Во втором наборе входных данных множества символов строк не пересекаются, поэтому никакая непустая строка не может быть общей подпоследовательностью.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
2
ABC
CBA
2
bacab
defed
3
abcde
aBcDe
ace
2
codeforces
technocup
|
1
A
0
3
ace
3
coc
|