Peculiar Movie Preferences
Contest: Codeforces Round 767 (Div. 1)
Difficulty rating: 1700
Tags: greedy, strings

Mihai plans to watch a movie. He only likes palindromic movies, so he wants to skip some (possibly zero) scenes to make the remaining parts of the movie palindromic.

You are given a list $$$s$$$ of $$$n$$$ non-empty strings of length at most $$$3$$$, representing the scenes of Mihai's movie.

A subsequence of $$$s$$$ is called awesome if it is non-empty and the concatenation of the strings in the subsequence, in order, is a palindrome.

Can you help Mihai check if there is at least one awesome subsequence of $$$s$$$?

A palindrome is a string that reads the same backward as forward, for example strings "z", "aaa", "aba", "abccba" are palindromes, but strings "codeforces", "reality", "ab" are not.

A sequence $$$a$$$ is a non-empty subsequence of a non-empty sequence $$$b$$$ if $$$a$$$ can be obtained from $$$b$$$ by deletion of several (possibly zero, but not all) elements.

Input format:
The first line of the input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the number of scenes in the movie.

Then follows $$$n$$$ lines, the $$$i$$$-th of which containing a single non-empty string $$$s_i$$$ of length at most $$$3$$$, consisting of lowercase Latin letters.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case, print "YES" if there is an awesome subsequence of $$$s$$$, or "NO" otherwise (case insensitive).

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first test case, an awesome subsequence of $$$s$$$ is $$$[ab, cc, ba]$$$

Example input:
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

Example output:
YES
NO
NO
YES
YES
NO

Editorial:
Because of the low constraints on the lengths of the strings, we can prove that it's enough to pair at most $$$2$$$ strings to form a palindrome.
<proof only checking pairs is enough>
Let's assume there is a awesome subsequence of the form xyz where x and z are single strings from s, and y is anything. If x and z are the same length, they clearly have to be reverses of each other for xyz to be a palindrome, so y is not needed to make it a palindrome. If they are not the same length, one of them is of length 3 and the other is of length 2. Assume x is the string of length 3 and y is the string of length 2. The first two characters of x must be the reverse of z. If x and z are concatenated, the third character of x is in the middle, so it doesn't matter. So in this case too, y is not needed. This proves that if any awesome subsequence exists, there also exists an awesome subsequence of 1 or 2 strings.
<proof ends>
So, we first check if there exists a palindrome already, if there is, we found a solution! If not, checking for each pair would take too long, but we can do it much more efficiently. We can assume that all strings are of length $$$2$$$ or $$$3$$$ since if there was a string of length $$$1$$$ it would be a palindrome and we would have found the solution earlier.
For each string of length $$$2$$$ it's enough to check if before it, we have seen a string of the following $$$2$$$ forms: its reverse or its reverse with a character appended to it (so a string of length $$$3$$$), since the last character of a string of length $$$3$$$ would be the middle character of the palindrome obtained after concatenation.
For each string of length $$$3$$$ it's enough to check if before it, we have seen a string of the following $$$2$$$ forms: its reverse or the reverse of the string without considering the first character (so a string of length $$$2$$$), since the first character of a string of length $$$3$$$ would be the middle character of the palindrome obtained after concatenation.
All this can be checked using a frequency matrix, map, set or other data structures.