TETRAVEX - Tetravex Puzzle

TetraVex is a challenging computer brain teaser. The object of the game is to fill the grid with the tiles so that the numbers on the adjacent edges of each tile match, much like aligning domino tiles.

Given the 9 tiles, you have to find out whether it is possible to solve the puzzle. Each tile is represented using 4 digits. A tile is given in the order A B C D in the clockwise direction starting from top cell. So the top left tile is denoted as ‘2 1 4 9’ and the bottom right as ‘2 1 6 6’. You cannot rotate the tiles, that is the original order must be preserved.

Input

There will be many cases in the input file. The first line gives the number of test cases (<= 20). Each case consists of 9 lines giving 4 integers each. Each line gives the information of a tile in the order A B C D. The tiles are randomly given.

Output

For each case, output YES or NO. Follow the sample for exact format

Example

Input:
2
2 8 4 6
1 1 3 5
0 4 2 8
2 5 3 3
7 6 0 4
7 3 0 6
4 8 7 7
0 3 1 2
2 2 2 8
1 1 1 1
2 2 2 2
3 3 3 3
4 4 4 4
5 5 5 5
6 6 6 6
7 7 7 7
8 8 8 8
9 9 9 9

Output:
Case 1: YES
Case 2: NO

Added by:Hemant Verma
Date:2009-11-17
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 NODEJS OBJC PERL6 SQLITE VB.NET
Resource:Alkhwarizm 2009

hide comments
2016-01-17 16:52:15
If you number each tile from 0 to 8 from top to bottom as given in sample input, solution (not sure if only) to first test case is:
0 2 4
6 8 7
5 3 1

Last edit: 2016-01-17 16:52:44
2015-06-01 03:10:25 Anderson Renoir
I liked to solve this problem!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.