CF1794A.Prefix and Suffix Array

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.

马尔科斯非常喜爱字符串，因此他有一个由小写英文字母组成的最爱字符串 $s$。对于该字符串，他将 $s$ 的所有非空前缀和后缀（不包括 $s$ 本身）以任意顺序写在一张纸上。你看到了纸上的所有这些字符串，并想知道马尔科斯的最爱字符串 $s$ 是否为回文串。因此，你的任务是仅根据这张纸上的字符串来判断 $s$ 是否为回文串。

若字符串 $a$ 可通过从字符串 $b$ 的末尾删除若干个（可能为零个或全部）字符得到，则称 $a$ 是 $b$ 的一个前缀。

若字符串 $a$ 可通过从字符串 $b$ 的开头删除若干个（可能为零个或全部）字符得到，则称 $a$ 是 $b$ 的一个后缀。

回文串是指正读与反读都相同的字符串，例如字符串 "gg"、"ioi"、"abba"、"icpci" 是回文串，但字符串 "codeforces"、"abcd"、"alt" 不是。

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.

每个测试包含多个测试用例。第一行包含一个整数 $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$ 本身），以任意顺序给出。

保证这些字符串恰好构成某个仅由小写英文字母组成的字符串的所有非空前缀与后缀。

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.

对于每个测试用例，如果 $s$ 是回文串，则输出 “YES”；否则输出 “NO”。

您可以以任意大小写形式输出答案（大写或小写均可）。例如，字符串 “yEs”、“yes”、“Yes” 和 “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$ 为 "abcd"。它的前缀是 "a"、"ab" 和 "abc"，后缀是 "d"、"cd" 和 "bcd"。由于字符串 "abcd" 不是回文串，答案为 NO。

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

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

在第四个测试用例中，$s$ 为 "alt"，它不是一个回文串。