교차 그래프

Innokentiy는 기하 알고리즘을 쓰는 일을 아직도 무척 좋아하지만, 삼각형 메시에서 입체로 옮겨 갔다. 그는 두 입체의 교차 그래프를 만드는 알고리즘을 작성하려 한다. 이 그래프는 예를 들어 두 입체에 대한 불리언 연산을 수행할 때 필요하다. 교차 그래프를 만들 때는 입체의 경계만 고려하고 내부 부피는 고려하지 않는다. Innokentiy는 임의의 두 입체에 대한 교차 그래프를 만드는 일이 CAD 분야에서 어려운 작업이라는 것을 안다. 그래서 난이도를 낮추었다. 먼저 두 박스 $A$, $B$의 교차 그래프를 만드는 법을 익히려 한다.

박스(보통 축에 정렬된 박스라고 부른다)는 각 변이 좌표축에 평행한 직육면체다. 박스의 경계는 세 종류의 위상 요소로 이루어진다.

• V: 꼭짓점. 기하학적으로 한 점이다.
• E: 모서리. 선분이다.
• F: 면. 직사각형이다.

각 박스에는 꼭짓점 8개, 모서리 12개, 면 6개가 있다.

이 문제에서는 모서리와 면을 경계점을 포함하지 않는 점 집합으로 나타낸다. 따라서 모서리는 끝점을 포함하지 않는 선분이고, 면은 꼭짓점과 변을 포함하지 않는 직사각형이다. 이 정의에 따르면 위상 요소는 서로 공통점이 없고, 합치면 박스의 경계 전체가 된다.

교차 그래프는 서로 연결된 교차 요소로 이루어지며, 교차 요소는 다음과 같이 정의된다. 박스 $A$의 위상 요소 $u$와 박스 $B$의 위상 요소 $v$의 모든 쌍을 고려한다(총 676쌍). 각 쌍 $(u,v)$에 대해 두 집합의 교집합을 구한다. 이 교집합이 비어 있지 않으면 하나의 교차 요소를 정의하며, 그 종류는 다음 세 가지 중 하나다.

• p: 점. 한 점이다.
• c: 곡선. 선분을 이루는 점 집합이다.
• s: 표면. 직사각형을 이루는 점 집합이다.

교차 그래프는 이렇게 얻은 모든 교차 요소로 이루어진다.

교차 요소는 서로 연결되어 있다. 각 교차 곡선에는 양 끝에 있는 두 교차점이 저장된다. 각 교차점에는 그 점에 부속된 교차 곡선의 목록이 저장된다. 교차 곡선은 자신의 끝점에만 부속되고 다른 교차점에는 부속되지 않는다. 각 교차 표면에는 그 경계에 있는, 따라서 표면을 둘러싸는 교차 곡선의 집합이 저장된다.

입력 파일의 첫 줄에는 테스트 케이스 수 $T$가 주어진다($1 \le T \le 5000$). 이어서 $T$개의 블록이 주어진다.

각 블록은 두 줄로 이루어진다. 첫째 줄은 박스 $A$, 둘째 줄은 박스 $B$를 정의한다. 박스는 절댓값이 $10^3$을 넘지 않는 여섯 정수 $x_1, y_1, z_1, x_2, y_2, z_2$로 정의된다. $x_1, y_1, z_1$은 최소 꼭짓점의 좌표이고, $x_2, y_2, z_2$는 최대 꼭짓점의 좌표이다($x_1 < x_2$, $y_1 < y_2$, $z_1 < z_2$).

출력 파일에는 입력 파일의 각 테스트 케이스에 대한 교차 그래프를 $T$개 출력한다. 각 교차 그래프 뒤에는 ===를 별도 줄에 출력한다. 출력 파일의 모든 수는 정수여야 한다.

교차 그래프 설명에는 교차 요소와 위상 요소 사이의 연결이 많이 등장한다. 이러한 연결을 나타내기 위해 모든 요소에 번호(또는 인덱스)를 붙인다. 박스 $A$의 모든 위상 요소에는 $1$부터 $26$까지의 정수를 임의의 순서로 붙인다. 마찬가지로 박스 $B$의 모든 위상 요소에도 $1$부터 $26$까지의 정수를 임의의 순서로 붙인다. 또한 모든 교차 요소에는 출력 파일에 나타나는 순서대로 $1$부터 $K$까지 번호를 붙인다. 여기서 $K$는 교차 요소의 총개수다.

교차 그래프 설명의 첫 줄에는 $P$ (교차점 수), $C$ (교차 곡선 수), $S$ (교차 표면 수)를 출력한다. 당연히 $P+C+S=K$이다. 그다음 교차 요소를 다음 순서로 설명한다. 먼저 $P$개의 교차점, 다음으로 $C$개의 교차 곡선, 마지막으로 $S$개의 교차 표면을 한 줄에 하나씩 출력한다.

각 교차 요소의 설명은 그 번호로 시작하고, 이어서 다음 규칙에 따라 만든 세 글자 코드를 출력한다.

1. 첫 글자는 교차 요소의 종류다. 점은 p, 곡선은 c, 표면은 s다.
2. 둘째 글자는 위상 요소 $u$의 종류다. 꼭짓점은 V, 모서리는 E, 면은 F다.
3. 셋째 글자는 위상 요소 $v$의 종류다.

여기서 $u$와 $v$는 각각 박스 $A$와 $B$의 위상 요소이며, 해당 교차 요소가 만들어진 두 요소다. 그다음 두 정수, 즉 $u$와 $v$의 번호를 이 순서대로 출력한다. 마지막으로 교차 요소의 종류에 따라 추가 정보를 출력한다.

교차점의 경우 위치 좌표 세 개, 부속된 교차 곡선의 수, 그 교차 곡선들의 번호 목록을 추가로 출력한다. 부속된 곡선의 번호는 임의의 순서로 출력해도 된다.

교차 곡선의 경우 양 끝에 있는 두 교차점의 번호를 추가로 출력한다. 두 번호는 임의의 순서로 출력해도 된다.

교차 표면의 경우 경계에 있는 교차 곡선의 수와 그 번호 목록을 추가로 출력한다. 경계 곡선의 번호는 임의의 순서로 출력해도 된다.

출력 파일에서 수들을 반드시 공백 하나로만 구분할 필요는 없다. 여러 개의 공백을 연속해서 사용해도 된다.

첫 번째 테스트 케이스에서는 두 박스가 꼭짓점으로 서로를 뚫고 지나간다. 교차 그래프는 굵은 선으로 표시되어 있다. 그래프는 여섯 개의 점과 여섯 개의 곡선으로 이루어지며, 박스 $B$ 때문에 관찰자에게 가려져 있다. 교차 요소의 번호가 표시되어 있다.

두 번째 테스트 케이스에서는 두 박스가 아래쪽 면과 앞쪽 면을 공유하므로 교차 표면 19와 20이 각각 생긴다(그림에는 나타나지 않는다). 나머지 요소는 모두 굵게 표시되어 있고 그 번호가 주어져 있다.