题目描述

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-aligned^{1}$ 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?

$^{1}Axis-aligned$ means that all segments are parallel to either $X , Y$ , or $Z$ axis.

输入格式

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 \le n \le 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.

题目大意

给定三维空间中 $n$ 个平行于坐标轴的空心 正方形，请判断是否有一种划分方案，使得所有矩形被划分为两个 非空 集合 $A,B$，且对于 $\forall i\in A,\forall j\in B$，矩形 $i,j$ 可以扣起来。

这里对“扣起来”的定义是：矩形 $A,B$ 各有一条边穿过另一个矩形，而它的对边则在另一个矩形外。可以尝试想象锁链环环相扣的样子。

不同矩形的边互不相交。多组数据，$n\le 10^6$。

3

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

5
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

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

NO
YES
YES

提示

Time limit: 10 s, Memory limit: 128 MB.