← 返回题目列表

Codeforces · 1628/B

B. 特殊的电影偏好

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

米海打算看电影。他只喜欢回文电影,所以他想跳过一些(可能是零)场景,使电影的其余部分成为回文。

给你一个 $$$s$$$ 的列表,其中包含 $$$n$$$ 个非空字符串,长度最多为 $$$3$$$,代表 Mihai 电影中的场景。

如果 $$$s$$$ 的子序列非空,并且子序列中字符串的按顺序连接是回文,则该子序列被称为 Awesome。

你能帮 Mihai 检查 $$$s$$$ 是否至少有一个很棒的子序列吗?

回文是向后读与向前读相同的字符串,例如字符串“z”、“aaa”、“aba”、“abccba”是回文,但字符串“codeforces”、“reality”、“ab”不是。

如果 $$$a$$$ 可以通过删除几个(可能为零,但不是全部)元素从 $$$b$$$ 获得,则序列 $$$a$$$ 是非空序列 $$$b$$$ 的非空子序列。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 电影中的场景数。

接下来是 $$$n$$$ 行,其中第 $$$i$$$ 包含单个非空字符串 $$$s_i$$$,长度最多为 $$$3$$$,由小写拉丁字母组成。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,如果存在 $$$s$$$ 的精彩子序列,则打印“YES”,否则打印“NO”(不区分大小写)。

示例

输入 #1

6
5
zx
ab
cc
zx
ba
2
ab
bad
4
co
def
orc
es
3
a
b
c
3
ab
cd
cba
2
ab
ab

输出 #1

YES
NO
NO
YES
YES
NO

注意

在第一个测试用例中, $$$s$$$ 的一个很棒的子序列是 $$$[ab, cc, ba]$$$