실뭉치와 뜨개바늘

Joana Vasconcelos는 다리미나 플라스틱 식기 같은 일상 용품으로 작품을 만드는 포르투갈 예술가다. 아나는 그 작업에서 영감을 받아, 곧은 뜨개바늘과 실뭉치로 천장에 매다는 조형물을 만들려고 한다. 안전을 위해 바늘 양쪽 끝에는 실뭉치를 하나씩 꽂는다. 뜨개바늘은 색과 길이와 굵기가 서로 달라서 바늘끼리 교차할 수 있다.

조형물은 방의 모서리에 전시한다. 모서리는 3차원 직교 좌표계를 이루고, 천장에는 조명이 여러 개 달려 있다. 설계도에는 뜨개바늘이 꽂힌 실뭉치의 중심 좌표를 적는다. 즉 바늘 $N$은 서로 다른 두 삼중항의 집합 $N = \{(x,y,z),(x',y',z')\}$으로 나타낸다.

아나는 닫힌 사슬을 싫어한다. 참 닫힌 사슬은 서로 다른 바늘 $k$개를 늘어놓은 수열 $N_1, N_2, ..., N_k$ ($k \ge 3$)로서 다음을 만족한다.

• $N_1 = \{(x_1,y_1,z_1),(x_2,y_2,z_2)\}$, $N_2 = \{(x_2,y_2,z_2),(x_3,y_3,z_3)\}$, ..., $N_k = \{(x_k,y_k,z_k),(x_{k+1},y_{k+1},z_{k+1})\}$이고, $(x_{k+1},y_{k+1},z_{k+1}) = (x_1,y_1,z_1)$이다.

닫힌 사슬을 싫어하는 정도가 심해서, 조형물이 바닥에 드리우는 그림자에도 바닥 닫힌 사슬이 없어야 한다. 바늘 $N = \{(x,y,z),(x',y',z')\}$의 바닥 그림자를 $N^{\downarrow} = \{(x,y),(x',y')\}$로 쓴다. 예술가인 아나에게 바닥 닫힌 사슬 역시 서로 다른 바늘 $k$개를 늘어놓은 수열 $N_1, N_2, ..., N_k$ ($k \ge 3$)로서 다음을 만족하는 것이다.

• 모든 $1 \le i < j \le k$에 대해 $N_i^{\downarrow} \ne N_j^{\downarrow}$이다. 즉 바늘 $k$개의 그림자가 모두 서로 다르다.
• $N_1^{\downarrow} = \{(x_1,y_1),(x_2,y_2)\}$, $N_2^{\downarrow} = \{(x_2,y_2),(x_3,y_3)\}$, ..., $N_k^{\downarrow} = \{(x_k,y_k),(x_{k+1},y_{k+1})\}$이고, $(x_{k+1},y_{k+1}) = (x_1,y_1)$이다.

뜨개바늘 네 개가 $A = \{(12,12,8),(10,5,11)\}$, $B = \{(12,12,8),(4,14,21)\}$, $C = \{(12,12,8),(12,20,8)\}$, $D = \{(4,14,21),(10,5,21)\}$인 조형물을 보자. 이 구조에는 참 닫힌 사슬이 없지만 $A, B, D$가 바닥 닫힌 사슬이므로, 닫힌 사슬이 없는 조형물은 아니다.

조형물의 뜨개바늘이 주어질 때, 참 닫힌 사슬이 있는지와 바닥 닫힌 사슬이 있는지 판정하는 프로그램을 작성하라.

첫째 줄에 조형물의 뜨개바늘 개수 $K$가 정수로 주어진다. 이어지는 $K$개의 줄에는 각각 정수 여섯 개 $x_1$, $y_1$, $z_1$, $x_2$, $y_2$, $z_2$가 주어지고, 이는 $\{(x_1,y_1,z_1),(x_2,y_2,z_2)\}$가 바늘 하나의 삼중항 집합임을 뜻한다. 한 바늘의 두 삼중항은 서로 다르고, 서로 다른 두 바늘은 서로 다른 삼중항 집합으로 주어진다.

두 줄에 각각 문자열 하나를 출력한다.

첫째 줄에는 조형물에 참 닫힌 사슬이 있으면 True closed chains를, 없으면 No true closed chains를 출력한다.

둘째 줄에는 조형물에 바닥 닫힌 사슬이 있으면 Floor closed chains를, 없으면 No floor closed chains를 출력한다.

• $1 \le K \le 50000$, 뜨개바늘의 개수
• $1 \le x_i, y_i, z_i \le 1000$, 각 삼중항의 좌표