← 返回题目列表

Codeforces · 1794/A

A. 前缀和后缀数组

中文机器翻译题面 查看原题

Marcos非常喜欢字符串,所以他最喜欢一个由小写英文字母组成的字符串$$$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”不是回文,所以答案是否定的。

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

在第三个测试用例中,$$$s$$$ 是“gg”,它是一个回文。

在第四个测试用例中,$$$s$$$ 是“alt”,它不是回文。