Wooden Stick Chain

Ruirui has a collection of wooden sticks. Each stick has two endpoints painted in some colors. He now has an idea: to arrange these sticks in a line such that the two touching ends of any two consecutive sticks have the same color. Given the colors at both ends of every stick, determine whether there exists an arrangement meeting the criteria.

This problem can be modeled as an Eulerian path problem on an undirected multigraph. Each unique color represents a vertex, and each stick represents an edge connecting the two colors. A valid chain exists if and only if:

• The graph is connected (ignoring isolated vertices), and
• Either every vertex has an even degree or exactly two vertices have an odd degree. In mathematical terms, if we denote the number of vertices with odd degree as odd, then a valid chain exists if $$ \text{odd} \in \{0, 2\}. $$

For example, if there are only 2 sticks with endpoints (red, blue) and (red, yellow), a valid chain would be:

blue — red | red — yellow

inputFormat

The first line contains an integer n representing the number of wooden sticks. Each of the next n lines contains two strings separated by spaces, representing the colors on the two endpoints of a stick.

outputFormat

Output YES if there exists an arrangement meeting the above criteria. Otherwise, output NO.

sample

2
red blue
red yellow

YES