Welcome To SDIBT ACM-ICPC Online Judge

VIRTUAL JUDGE Recent Contest F.A.Qs Discuss Home ProblemSet Status Ranklist Contest LoginRegister Exam
Problem 1083. -- Tower of Cubes

Tower of Cubes

Time Limit: 1 Sec  Memory Limit: 64 MB
Submit: 9  Solved: 0
[Submit][Status][Discuss]

Description

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 different color. Your job is to build the tallest possible tower of cubes subject to the restrictions that (1) we never put a heavier cube on a lighter one, and (2) the bottom face of every cube (except the bottom one) must have the same color as the top face of the cube below it.

Input

The input may contain several test cases. The first line of each test case contains an integer N ( 1<=N<=500) indicating the number of cubes you are given. The ith of the next N lines contains the description of the ith 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 colors are identified by integers in the range 1 to 100. 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 a value 0 for N.

Output

For each case, start by printing the test case number on its own line as shown in the sample output. On the next line, print the number of cubes in the tallest possible tower. The next line describes the cubes in your tower from top to bottom with one description per line. Each description gives the serial number of this cube in the input, followed by a single white­space character and then the identification string (front, back, left, right, top, or bottom of the top face of the cube in the tower. There may be multiple solutions, but any one of them is acceptable. Print a blank line between two successive test cases.

Sample Input

3
1 2 2 2 1 2
3 3 3 3 3 3
3 2 1 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

Sample Output

Case #1
2
2 front
3 front
 
Case #2
8
1 bottom
2 back
3 right
4 left
6 top
8 front
9 front
10 top

HINT

Source

[Submit][Status][Discuss]

HOME Back

한국어 中文 English
All Copyright Reserved 2008-2010 SDIBT TEAM
GPL2.0 2003-2010 HUSTOJ Project TEAM
Anything about the Problems, Please Contact Admin:admin