Prefix and Suffix Array

题意翻译

马科斯非常喜爱字符串，他有一个最爱的字符串 $s$，里面只由小写英文字母组成。 对于这个字符串 $s$，马科斯在一张纸上胡乱写下了 $s$ 的所有**非空真前缀子串**和**非空真后缀子串**（因为是胡乱写下的，所以这并没有什么顺序）。你看到了这张纸，看到了写在上面的所有字符串，现在你很好奇：马科斯最爱的字符串 $s$ 是不是一个**回文串**。 你的任务是：利用字符串 $s$ 的所有**非空真前缀子串**和**非空真后缀子串**，判断 $s$ 是否是一个**回文串**。 一个字符串 $a$ 是另一个字符串 $b$ 的**非空真前缀子串**，当且仅当从 $b$ 的末尾删去一部分后，剩下的一部分就是 $a$。 一个字符串 $a$ 是另一个字符串 $b$ 的**非空真后缀子串**，当且仅当从 $b$ 的开头删去一部分后，剩下的一部分就是 $a$。 一个**回文串**从前往后读和从后往前读是一模一样的。例如，字符串 $\texttt{gg}$，$\texttt{ioi}$，$\texttt{abba}$，$\texttt{icpci}$ 是回文串，而字符串 $\texttt{codeforces}$，$\texttt{abcd}$，$\texttt{alt}$ 不是回文串。

题目描述

Marcos loves strings a lot, so he has a favorite string $ s $ consisting of lowercase English letters. For this string, he wrote down all its non-empty prefixes and suffixes (except for $ s $ ) on a piece of paper in arbitrary order. You see all these strings and wonder if Marcos' favorite string is a palindrome or not. So, your task is to decide whether $ s $ is a palindrome by just looking at the piece of paper. A string $ a $ is a prefix of a string $ b $ if $ a $ can be obtained from $ b $ by deletion of several (possibly, zero or all) characters from the end. A string $ a $ is a suffix of a string $ b $ if $ a $ can be obtained from $ b $ by deletion of several (possibly, zero or all) characters from the beginning. A palindrome is a string that reads the same backward as forward, for example, strings "gg", "ioi", "abba", "icpci" are palindromes, but strings "codeforces", "abcd", "alt" are not.

输入输出格式

输入格式

Each test consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \le t \le 120 $ ) — the number of test cases. The description of test cases follows. The first line of each test case contains a single integer $ n $ ( $ 2\le n \le 20 $ ) — the length of the string $ s $ . The second line of each test case contains $ 2n-2 $ strings $ a_1, a_2, \cdots, a_{2n-2} $ — all non-empty prefixes and suffixes of $ s $ , not including itself, in arbitrary order. It is guaranteed that these strings are all the non-empty prefixes and suffixes of some string consisting of lowercase English letters.

输出格式

For each test case, output "YES" if $ s $ is a palindrome, and "NO" otherwise. You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

输入输出样例

输入样例 #1

5
4
bcd cd a d abc ab
3
i io i oi
2
g g
3
t al lt a
4
bba a ab a abb ba

输出样例 #1

NO
YES
YES
NO
YES

说明

In the first test case, $ s $ is "abcd". Its prefixes are "a", "ab" and "abc", and its suffixes are "d", "cd" and "bcd". As the string "abcd" is not a palindrome, the answer is NO. In the second test case, $ s $ is "ioi". Its prefixes are "i" and "io", and its suffixes are "i" and "oi". As the string "ioi" is a palindrome, the answer is YES. In the third test case, $ s $ is "gg" which is a palindrome. In the fourth test case, $ s $ is "alt" which is not a palindrome.

**前缀和后缀数组**

**题意翻译**
马科斯非常喜欢字符串，他有一个最爱的字符串 $ s $，里面只由小写英文字母组成。对于这个字符串 $ s $，马科斯在一张纸上胡乱写下了 $ s $ 的所有**非空真前缀子串**和**非空真后缀子串**（因为是胡乱写下的，所以这并没有什么顺序）。你看到了这张纸，看到了写在上面的所有字符串，现在你很好奇：马科斯最爱的字符串 $ s $ 是不是一个**回文串**。

你的任务是：利用字符串 $ s $ 的所有**非空真前缀子串**和**非空真后缀子串**，判断 $ s $ 是否是一个**回文串**。

一个字符串 $ a $ 是另一个字符串 $ b $ 的**非空真前缀子串**，当且仅当从 $ b $ 的末尾删去一部分后，剩下的一部分就是 $ a $。

一个字符串 $ a $ 是另一个字符串 $ b $ 的**非空真后缀子串**，当且仅当从 $ b $ 的开头删去一部分后，剩下的一部分就是 $ a $。

一个**回文串**从前往后读和从后往前读是一模一样的。例如，字符串 $\texttt{gg}$，$\texttt{ioi}$，$\texttt{abba}$，$\texttt{icpci}$ 是回文串，而字符串 $\texttt{codeforces}$，$\texttt{abcd}$，$\texttt{alt}$ 不是回文串。

**题目描述**
马科斯喜欢字符串，他有一个由小写英文字母组成的喜爱字符串 $ s $。对于这个字符串，他按任意顺序写下所有它的非空前缀和非空后缀（除了 $ s $ 本身）在一张纸上。你看到所有这些字符串，并想知道马科斯的喜爱字符串是否是一个回文串。所以，你的任务是仅通过查看这张纸来判断 $ 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 $ 是一个回文串，输出 "YES"，否则输出 "NO"。

你可以以任何大小写输出答案。例如，"yEs"、"yes"、"Yes" 和 "YES" 都将被认为是肯定的回答。

**输入输出样例**

**输入样例 #1**
```
5
4
bcd cd a d abc ab
3
i io i oi
2
g g
3
t al lt a
4
bba a ab a abb ba
```
**输出样例 #1**
```
NO
YES
YES
NO
YES
```

**说明**
在第一个测试用例中，$ s $ 是 "abcd"。它的前缀是 "a"、"ab" 和 "abc"，后缀是 "d"、"cd" 和 "bcd"。因为字符串 "abcd" 不是回文串，答案是 NO。

在第二个测试用例中，$ s $ 是 "ioi"。它的前缀是 "i" 和 "io"，后缀是 "i" 和 "oi"。因为字符串 "ioi" 是回文串，答案是 YES。

在第三个测试用例中，$ s $ 是 "gg" 它是回文串。

在第四个测试用例中，$ s $ 是 "alt" 它不是回文串。**前缀和后缀数组** **题意翻译** 马科斯非常喜欢字符串，他有一个最爱的字符串 $ s $，里面只由小写英文字母组成。对于这个字符串 $ s $，马科斯在一张纸上胡乱写下了 $ s $ 的所有**非空真前缀子串**和**非空真后缀子串**（因为是胡乱写下的，所以这并没有什么顺序）。你看到了这张纸，看到了写在上面的所有字符串，现在你很好奇：马科斯最爱的字符串 $ s $ 是不是一个**回文串**。 你的任务是：利用字符串 $ s $ 的所有**非空真前缀子串**和**非空真后缀子串**，判断 $ s $ 是否是一个**回文串**。 一个字符串 $ a $ 是另一个字符串 $ b $ 的**非空真前缀子串**，当且仅当从 $ b $ 的末尾删去一部分后，剩下的一部分就是 $ a $。 一个字符串 $ a $ 是另一个字符串 $ b $ 的**非空真后缀子串**，当且仅当从 $ b $ 的开头删去一部分后，剩下的一部分就是 $ a $。 一个**回文串**从前往后读和从后往前读是一模一样的。例如，字符串 $\texttt{gg}$，$\texttt{ioi}$，$\texttt{abba}$，$\texttt{icpci}$ 是回文串，而字符串 $\texttt{codeforces}$，$\texttt{abcd}$，$\texttt{alt}$ 不是回文串。 **题目描述** 马科斯喜欢字符串，他有一个由小写英文字母组成的喜爱字符串 $ s $。对于这个字符串，他按任意顺序写下所有它的非空前缀和非空后缀（除了 $ s $ 本身）在一张纸上。你看到所有这些字符串，并想知道马科斯的喜爱字符串是否是一个回文串。所以，你的任务是仅通过查看这张纸来判断 $ 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 $ 是一个回文串，输出 "YES"，否则输出 "NO"。 你可以以任何大小写输出答案。例如，"yEs"、"yes"、"Yes" 和 "YES" 都将被认为是肯定的回答。 **输入输出样例** **输入样例 #1** ``` 5 4 bcd cd a d abc ab 3 i io i oi 2 g g 3 t al lt a 4 bba a ab a abb ba ``` **输出样例 #1** ``` NO YES YES NO YES ``` **说明** 在第一个测试用例中，$ s $ 是 "abcd"。它的前缀是 "a"、"ab" 和 "abc"，后缀是 "d"、"cd" 和 "bcd"。因为字符串 "abcd" 不是回文串，答案是 NO。 在第二个测试用例中，$ s $ 是 "ioi"。它的前缀是 "i" 和 "io"，后缀是 "i" 和 "oi"。因为字符串 "ioi" 是回文串，答案是 YES。 在第三个测试用例中，$ s $ 是 "gg" 它是回文串。 在第四个测试用例中，$ s $ 是 "alt" 它不是回文串。