Dominoes

A domino contains two ends, each labeled with number between 1 and 6. You are to write a program that determines if a set of dominoes can be organized in a line so that all dominoes are used; numbers on successive dominoes match; and the numbers on both ends match. You are allowed to rearrange and flip the dominoes arbitrarily. For example, the five dominos: (3 3), (3 1), (4 3), (1 6), and (4 6) can be arranged as:

The five dominos: (4 5), (3 4), (1 2), (2 3), and (5 5) cannot be arranged with all ends matching.

The input contains a list of domino-sets. The first line of each set contains a single integer corresponding to the number of dominos in the set – 3 <= N <= 10. The next N lines each contain the two values on a single domino. The end of input is denoted by N = 0.

Your program should produce one line of output for every set of dominos. The format should be: “Set #1: YES” or “Set #1: NO”.

3
1 2
3 2
3 1
5
4 5
3 4
1 2
2 3
5 5
5
3 3
3 1
4 3
1 6
4 6
0

Set #1: YES
Set #2: NO
Set #3: YES

2008 ACM ICPC Regional hangzhou

HDU “Valentines Day” Open Programming Contest 2009-02-14