1304B.md (1974B)
1 Source: https://codeforces.com/problemset/problem/1304/B 2 3 B. Longest Palindrome 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Returning back to problem solving, Gildong is now studying about palindromes. He learned that a palindrome is a string that is the same as its reverse. For example, strings "pop", "noon", "x", and "kkkkkk" are palindromes, while strings "moon", "tv", and "abab" are not. An empty string is also a palindrome. 22 23 Gildong loves this concept so much, so he wants to play with it. He has $n$ distinct strings of equal length $m$. He wants to discard some of the strings (possibly none or all) and reorder the remaining strings so that the concatenation becomes a palindrome. He also wants the palindrome to be as long as possible. Please help him find one. 24 25 Input 26 27 The first line contains two integers $n$ and $m$ ($1 \le n \le 100$, $1 \le m \le 50$) — the number of strings and the length of each string. 28 29 Next $n$ lines contain a string of length $m$ each, consisting of lowercase Latin letters only. All strings are distinct. 30 31 Output 32 33 In the first line, print the length of the longest palindrome string you made. 34 35 In the second line, print that palindrome. If there are multiple answers, print any one of them. If the palindrome is empty, print an empty line or don't print this line at all. 36 37 Examples 38 39 Input 40 41 ``` 42 3 3 43 tab 44 one 45 bat 46 ``` 47 48 Output 49 50 ``` 51 6 52 tabbat 53 ``` 54 55 Input 56 57 ``` 58 4 2 59 oo 60 ox 61 xo 62 xx 63 ``` 64 65 Output 66 67 ``` 68 6 69 oxxxxo 70 ``` 71 72 Input 73 74 ``` 75 3 5 76 hello 77 codef 78 orces 79 ``` 80 81 Output 82 83 ``` 84 0 85 ``` 86 87 Input 88 89 ``` 90 9 4 91 abab 92 baba 93 abcd 94 bcde 95 cdef 96 defg 97 wxyz 98 zyxw 99 ijji 100 ``` 101 102 Output 103 104 ``` 105 20 106 ababwxyzijjizyxwbaba 107 ``` 108 109 Note 110 111 In the first example, "battab" is also a valid answer. 112 113 In the second example, there can be 4 different valid answers including the sample output. We are not going to provide any hints for what the others are. 114 115 In the third example, the empty string is the only valid palindrome string.