You are given \(n\) colorful cubes, each having a distinct weight. Cubes are not monochromatic; indeed, every face of a cube is colored with a color. Your job is to build the tallest possible tower of cubes subject to two restrictions:
The input may contain several test cases separated by a blank line. The first line of each test case contains an integer \(n\) (\(1 \leq n \leq 500\)) indicating the number of cubes you are given. The \(i\)th of the next \(n\) lines contains the description of the \(i\)th cube. A cube is described by giving the colors of its faces in the following order: front, back, left, right, top, and bottom face. For your convenience (and because we care) colors are identified by integers in the range 1 to 100 (thus, more colors than most computer scientists can distinguish). You may assume that cubes are given in increasing order of their weights; that is, cube 1 is the lightest and cube \(n\) is the heaviest.
The input terminates with \(n=0\).
For each test case, print the number of cubes in the tallest possible tower on a separate line.
3
1 2 2 2 1 2
3 3 3 3 3 3
3 2 1 1 1
10
1 5 10 3 6 5
2 6 7 3 6 9
5 7 3 2 1 9
1 3 3 5 8 10
6 6 2 2 4 4
1 2 3 4 5 6
10 9 8 7 6 5
6 1 2 3 4 7
1 2 3 3 2 1
3 2 1 1 2 3
0
2
8
This is based on challenge 10051 of the ACM International Collegiate Programming Contest. Test input is provided by uDebug.
Please log in to submit your solution.
Difficulty 

Average test runtime  0.25 
Points (changes over time)  10 
Tried by  3 users 
Solved by  3 users 
#  Name  Runtime  Points worth 

1  Pascal  0.14  15 
2  贝尔恩德  0.22  10 
3  Mac  0.38  6 