#11169. A. Prefix and Suffix Array前缀和后缀数组

A. Prefix and Suffix Array前缀和后缀数组

题目:前缀和后缀数组

每个测试的时间限制: 1 秒 ⏳ 内存限制: 256 兆字节 💾

马科斯非常喜欢字符串,所以他有一个最喜欢的字符串 s,由小写英文字母组成。对于这个字符串,他写下了它的所有非空前缀和后缀(不包括 s)在一张纸上,按任意顺序排列。你看到所有这些字符串并想知道马科斯最喜欢的字符串是否是一个回文串。因此,你的任务是通过查看这张纸来决定字符串 s 是否是一个回文串。

字符串 a 是字符串 b 的前缀,如果 a 可以通过删除 b 末尾的若干(可能是零或全部)字符得到。

字符串 a 是字符串 b 的后缀,如果 a 可以通过删除 b 开头的若干(可能是零或全部)字符得到。

回文串是一个正向和反向读都相同的字符串,例如,字符串 "gg"、"ioi"、"abba"、"icpci" 是回文串,但字符串 "codeforces"、"abcd"、"alt" 不是。


输入

每个测试由多个测试用例组成。输入的第一行包含一个整数 t(1≤t≤120)——测试用例的数量。🌟

每个测试用例的第一行包含一个整数 n(2≤n≤20)——字符串 s 的长度。

每个测试用例的第二行包含 2n−2 个字符串 a1,a2,...,a2n−2——字符串 s 的所有非空前缀和后缀,不包括 s 本身,按任意顺序排列。

保证这些字符串都是由小写英文字母组成的某个字符串的所有非空前缀和后缀。


输出

对于每个测试用例,如果字符串 s 是回文串,输出 "YES";否则输出 "NO"。

你可以用任意大小写输出。例如,字符串 "yEs"、"yes"、"Yes" 和 "YES" 都会被识别为肯定回答。


示例

输入

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

输出

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",它不是一个回文串。 😊📚