#P16935. [SGU327]Yet Another Palindrome

[SGU327]Yet Another Palindrome

题目描述

给定 NN 个单词。请找出一个最短的回文串,使得给出的每个单词都作为它的一个连续子串出现。

回文串是指正着读与反着读完全相同的字符串。

输入格式

第一行包含一个整数 NN:

1≤N≤141\le N\le14。

接下来 NN 行,每行包含一个单词。每个单词长度在 11 到 3030 之间,并且只包含小写英文字母 a~z。

输出格式

输出满足要求的最短回文串。

如果存在多个最短答案,输出任意一个即可。

样例 1

1
avtobus
avtobusubotva

样例 2

3
bacd
edcab
cabac
edcabacde

说明

第二个样例中,输出串 edcabacde 是回文串,并且包含 bacd、edcab、cabac 三个给定单词作为连续子串。