CF1794A Prefix and Suffix Array

Marcos 非常喜欢字符串，他有一个最喜欢的字符串 $s$，由小写英文字母组成。对于这个字符串，他把所有非空前缀和后缀（不包括 $s$ 本身）都写在一张纸上，顺序是任意的。你现在能看到这些字符串，你想知道 Marcos 最喜欢的字符串是不是回文串。因此，你的任务是仅通过纸上的这些字符串判断 $s$ 是否为回文串。 如果字符串 $a$ 可以通过从字符串 $b$ 的末尾删除若干（可能为零或全部）字符得到，则称 $a$ 是 $b$ 的前缀。 如果字符串 $a$ 可以通过从字符串 $b$ 的开头删除若干（可能为零或全部）字符得到，则称 $a$ 是 $b$ 的后缀。 回文串是指正着读和反着读都相同的字符串。例如，"gg"、"ioi"、"abba"、"icpci" 都是回文串，而 "codeforces"、"abcd"、"alt" 不是回文串。

每组测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 120$）——表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 20$）——表示字符串 $s$ 的长度。 每个测试用例的第二行包含 $2n-2$ 个字符串 $a_1, a_2, \cdots, a_{2n-2}$——即 $s$ 的所有非空前缀和后缀（不包括 $s$ 本身），顺序任意。 保证这些字符串确实是某个由小写英文字母组成的字符串的所有非空前缀和后缀。

对于每个测试用例，如果 $s$ 是回文串，输出 "YES"；否则输出 "NO"。 你可以用任意大小写输出答案，例如 "yEs"、"yes"、"Yes" 和 "YES" 都会被认为是肯定回答。

在第一个测试用例中，$s$ 是 "abcd"。它的前缀有 "a"、"ab" 和 "abc"，后缀有 "d"、"cd" 和 "bcd"。由于字符串 "abcd" 不是回文串，答案是 NO。 在第二个测试用例中，$s$ 是 "ioi"。它的前缀有 "i" 和 "io"，后缀有 "i" 和 "oi"。由于字符串 "ioi" 是回文串，答案是 YES。 在第三个测试用例中，$s$ 是 "gg"，它是回文串。 在第四个测试用例中，$s$ 是 "alt"，它不是回文串。 由 ChatGPT 4.1 翻译