Chain & Co.

Chain & Co. specializes in producing infinitely strong chains. Because of their high quality products, they are quickly gaining market share. This leads to new challenges, some of which they could have never imagined before. Like, for example, automatic verification of link endurance with a computer program, which you are supposed to write.

The company produces links of equal size. Each link is an infinitely thin square frame in three dimensions (made of four infinitely thin segments).

During tests all links are axis-aligned1 and placed so that no two frames touch. To make a proper strength test, two sets of links $A$ and $B$ are forged so that every link of $A$ is inseparable from every link of $B$ (being inseparable means that they cannot be moved apart without breaking one of them).

You stumble upon some links (axis-aligned, pairwise disjoint). Are they in proper testing position? In other words, can they be divided into two non-empty sets $A$ and $B$ with the desired property?


The first line of input contains the number of test cases $T$. The descriptions of the test cases follow:

The description of each test case starts with an empty line. The next line contains an integer $n$, $1 \leq n \leq 10^6$—the number of links in the chain. Each of the next $n$ lines contains 6 space-separated integers $x_ i$, $y_ i$, $z_ i$, $x_ i’$, $y_ i’$, $z_ i’$, all between $-10^9$ and $10^9$—the coordinates of two opposite corners of the $i$-th link.


For each test case, print a single line containing the word YES if the set is in proper testing position, or NO otherwise.

Sample Input 1 Sample Output 1

0 0 0 0 10 10
-5 5 15 5 5 25

0 0 0 0 10 10
-5 5 6 5 5 16
-5 5 -6 5 5 4
-5 6 5 5 16 5
-5 -6 5 5 4 5

0 0 0 3 0 -3
1 -1 -1 1 2 -4
-1 -2 -2 2 1 -2


  1. Axis-aligned means that all segments are parallel to either $X$, $Y$, or $Z$ axis.
CPU Time limit 6 seconds
Memory limit 1024 MB
Statistics Show
License For educational use only

Please log in to submit a solution to this problem

Log in