가장 긴 회문
면접 대비시간 제한1초메모리 제한256 MB
길이가 같고 서로 다른 문자열들 중 일부를 골라 순서를 정해 이어 붙였을 때 가장 긴 회문을 만들고, 그 회문 하나를 출력합니다.
문제
길동이는 다시 문제 풀이로 돌아와서 지금은 회문(palindrome)을 공부하고 있다. 회문은 앞에서 읽든 뒤에서 읽든 같은 문자열이다. 예를 들어 "pop", "noon", "x", "kkkkkk"은 회문이고, "moon", "tv", "abab"은 회문이 아니다. 빈 문자열도 회문이다.
길동이에게는 길이가 모두 으로 같은 서로 다른 문자열 개가 있다. 길동이는 문자열 일부를 버리고(하나도 버리지 않거나 전부 버려도 된다) 남은 문자열의 순서를 바꿔서, 이어 붙인 결과가 회문이 되게 하려고 한다. 가능한 한 긴 회문을 만들고 싶다. 그런 회문을 하나 찾아라.
입력
첫째 줄에 두 정수 과 이 주어진다(, ). 은 문자열의 개수이고, 은 각 문자열의 길이이다.
이어서 개의 줄에 길이가 인 문자열이 한 줄에 하나씩 주어진다. 문자열은 소문자 라틴 알파벳으로만 이루어진다. 모든 문자열은 서로 다르다.
출력
첫째 줄에 만든 가장 긴 회문의 길이를 출력한다.
둘째 줄에 그 회문을 출력한다. 답이 여러 개이면 그중 아무것이나 출력해도 된다. 회문이 빈 문자열이면 빈 줄을 출력하거나 이 줄을 출력하지 않아도 된다.
힌트
첫 번째 예제에서는 "battab"도 올바른 답이다.
두 번째 예제에서는 예시 출력을 포함해 올바른 답이 4가지 있다. 나머지 답은 알려주지 않는다.
세 번째 예제에서는 빈 문자열만이 유일한 올바른 회문이다.