Tesseract 3-Net Folding

In this problem you are given a tree‐like octocube in 3D space. An octocube is a connected collection of 8 unit cubical cells joined face‐to‐face (two cells are adjacent if they share a full unit square). The octocube is tree–like in the sense that its adjacency graph (with a vertex per cell and an edge for every pair of cells that share a unit square) forms a tree.

A (solid) tesseract is the 4D analogue of a cube, and its boundary consists of 8 cells (which are cubes) meeting face–to–face. A 3–net of a tesseract is obtained by cutting 17 of its 24 square faces so that the remaining 7 faces keep the cells connected, and then unfolding the cells onto a 3D hyperplane. In other words, one may ask: given a tree–like octocube, is it possible to fold it in 4D along its shared square faces so that it forms the surface of a tesseract?

More formally, assume that the 8 cubes of a tesseract are identified with the 8 facets of a 4–cube. In a 4–cube (i.e. the hypercube) the facets are given by [ F = {(i,b): i=1,2,3,4,; b\in{0,1}}, ] where the facet ((i,b)) is the set of points in ([0,1]^4) with the (i\textth coordinate equal to (b). Two different facets ((i,b)) and ((j,c)) share a common 3D face (i.e. are adjacent in the tesseract) if and only if (i\ne j).

Your task is to determine whether the given tree–like octocube (specified by the positions of its 8 cells in 3D) can be folded into a tesseract. That is, is there a bijection from the 8 cube cells to the set of tesseract facets (F) such that for every pair of adjacent cells in the octocube the corresponding tesseract facets come from different indices (i.e. if one cell is assigned ((i,\cdot)) and the adjacent one is assigned ((j,\cdot)), then (i\ne j))?

Input/Output note: You do not need to simulate the folding process. It suffices to check whether there is an assignment of facets to cells (from the set (F)) that respects the face–to–face adjacency structure of the octocube.

Summary: Given a tree–like octocube (8 unit cubes in 3D space) with each pair of adjacent cubes sharing a full unit square, decide if it constitutes a 3–net of a tesseract by verifying the existence of a bijective mapping from the cubes to facets ((i,b)) ((i=1,2,3,4) and (b\in{0,1})) such that adjacent cubes are not assigned facets with the same index.

inputFormat

The first line of input contains an integer (T) ((1 \le T \le 10)), the number of test cases. Each test case consists of 8 lines. Each of these 8 lines contains three space–separated integers (x), (y), (z) ((|x|,|y|,|z| \le 10^9)) representing the coordinates of a unit cube (cell) in the octocube. Two cubes are considered adjacent if the Manhattan distance between their coordinates is exactly 1.

outputFormat

For each test case, output a single line containing “YES” if the given octocube can be folded into a tesseract (i.e. it constitutes a valid 3–net), and “NO” otherwise.

sample

3
0 0 0
1 0 0
-1 0 0
0 1 0
0 -1 0
0 0 1
0 0 -1
0 0 2
0 0 0
1 0 0
-1 0 0
0 1 0
0 -1 0
0 0 1
0 0 -1
1 0 1
5 5 5
6 5 5
4 5 5
5 6 5
5 4 5
5 5 6
5 5 4
5 5 7

YES
NO
YES