| Problem D The dominoes solitaire |
A man used to play dominoes with some friends in a small town. Some families have left the town and at present the only residents in the town are the man and his wife. This man would like to continue playing dominoes, but his wife does not like plaing. He has invented a game to play alone. Two pieces are picked out and are put at the two extremes of a row with a number (n) of spaces. After that, other pieces (m) are picked out to fill the spaces. The number of pieces is greater than or equal to the number of spaces (m>=n), and the number of pieces is less than or equal to 14 (m<=14). The spaces are filled by putting one piece in each space, accoding to the rules of dominoes: the number of adjacent dots on two different dominoes must coincide. Pieces with repeated values are placed in the same way as the other pieces, and not at right angels.
The problem consists in the design of a program which, given a number of spaces (n), a number of pieces (m), the two initial pieces (i1,i2) and (d1,d2), and the m pieces (p1,q1), (p2,q2), ..., (pm,qm), decides if it is possible to fill the n spaces between the two initial pieces using the m pieces and with the rules of dominoes. For example, with n=3, m=4, initial pieces (0,1) and (3,4), and pieces (2,1), (5,6), (2,2) and (3,2), the answer is YES, because there is a solution: (0,1), (1,2), (2,2), (2,3), (3,4). With n=2, m=4, pieces in the extremes (0,1) and (3,4), and (1,4), (4,4), (3,2) and (5,6), the answer is NO.
The input will consist of a series of problems, with each problem described in a series of lines: in the first line the number of spaces (n) is indicated, in the second line the number of pieces (m) used to fill the spaces, in the next line the piece to be placed on the left, with the two values in the piece separated by a space and in the same way that the numbers appear in the row, in the following lines the piece to be placed on the right, with the two values in the piece separated by a space and in the same way that the numbers appear in the row, and the other m pieces appear in consecutive lines, one in each line, with the two values separated by a space. Different problems appear in the input successively without separation, and the input finishes when 0 appears as the number of spaces.
For each problem in the input a line is written, with YES if the problem has a solution, and NO if it has no solution.
3
4
0 1
3 4
2 1
5 6
2 2
3 2
2
4
0 1
3 4
1 4
4 4
3 2
5 6
0
YES
NO