Circle of Words

You are given a list of words. Your task is to determine if it is possible to arrange all the words in a circle such that for every two consecutive words, the last character of the preceding word matches the first character of the next word, and the last word links back to the first word.

In other words, given words \(w_1, w_2, \dots, w_n\), determine if there exists a permutation so that

\(\forall i, \text{last}(w_i) = \text{first}(w_{(i \mod n) + 1})\)

Return YES if such a permutation exists, or NO otherwise.

inputFormat

The first line contains an integer T indicating the number of test cases.

For each test case:

• The first line contains an integer N, the number of words.
• The second line contains N space-separated strings representing the words.

outputFormat

For each test case, output a single line with YES if the words can form a circle, or NO otherwise.

1
4
ab bc cd da

YES