Rearrange Words into a Chain

You are given a list of words. Your task is to determine if it is possible to rearrange these words into a chain, such that the last character of each word is equal to the first character of the next word.

This problem can be modeled as finding an Eulerian path in a directed graph. Each word represents an edge from its first letter to its last letter. A necessary condition is that the graph constructed from the words is connected (when regarded as an undirected graph) and that the in-degree and out-degree of each vertex satisfy Eulerian path conditions. In particular, either every vertex has equal in-degree and out-degree (an Eulerian circuit exists) or exactly one vertex has out-degree equal to in-degree plus one (start vertex) and exactly one vertex has in-degree equal to out-degree plus one (end vertex).

If these conditions hold, output YES; otherwise, output NO.

inputFormat

The first line contains an integer n representing the number of words. Each of the following n lines contains one word consisting of alphabetic characters.

outputFormat

Output a single line: YES if it is possible to rearrange the words to form a valid chain, otherwise NO.

3
abc
cde
efg

YES