Strange LCS

题意翻译

- 给定 $n$ 个字符串 $s_i$，每个字符串只包含大写和小写英文字母，且每个字母在每个字符串中最多出现两次。 - 求这些字符串的最长公共子序列。 - 多组数据。

题目描述

You are given $ n $ strings $ s_1, s_2, \ldots, s_n $ , each consisting of lowercase and uppercase English letters. In addition, it's guaranteed that each character occurs in each string at most twice. Find the longest common subsequence of these strings. A string $ t $ is a subsequence of a string $ s $ if $ t $ can be obtained from $ s $ by deletion of several (possibly, zero or all) symbols.

输入输出格式

输入格式

Each test consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 5 $ ) — the number of test cases. Description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 2 \leq n \leq 10 $ ) — the number of strings. Each of the next $ n $ lines contains the corresponding string $ s_i $ . Each $ s_i $ is non-empty, consists only of uppercase and lowercase English letters, and no character appears more than twice in each string.

输出格式

For each test case print the answer in two lines: In the first line print the length of the longest common subsequence. In the second line print the longest common subsequence. If there are multiple such subsequences, print any of them.

输入输出样例

输入样例 #1

4
2
ABC
CBA
2
bacab
defed
3
abcde
aBcDe
ace
2
codeforces
technocup

输出样例 #1

1
A
0

3
ace
3
coc

说明

In the first test case, the longest common subsequence is "A". There are no common subsequences of length $ 2 $ . In the second test case, sets of characters of strings don't intersect, so any non-empty string can't be a common subsequence.