Vasya, the bus conductor who likes to look
for lucky tickets, is also good at playing dominoes. One day someone brought
him a number of domino tiles, and he wondered if it would be possible to use
all the tiles making a valid line of play, meaning that adjacent tiles touch
with an equal number of spots. See an example below (the line makes turns in
the figure):
Note: each domino is a 1x2 rectangular tile
consisting of two squares (ends). Each end is marked with up to 6 spots or is
blank.
Your task is to write a program that
determines if it is possible to make a continuous line of play using a given
set of n tiles. Adjacent tiles in the line must have an equal
number of spots on the touching ends.
Limitations
1 £
n £ 1000.
Input
The first line of the input file contains
an integer n, the number of tiles in the set. The following n
lines describe the tiles. Each line contains two space-delimited integers from
0 to 6, the number of spots on the two ends of a tile.
Output
The program should output a single string
(without quotation marks): “YES” if it is possible to make a continuous line of
play using the given tiles, or “NO”, otherwise.
Example
|
Input
|
Output
|
|
2
1 2
1 3
|
YES
|
|
3
1 2
1 3
1 4
|
NO
|
|
2
1 2
3 4
|
NO
|
