P7014 [CERC2013] 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-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.

输入格式

输出格式

说明/提示

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