문어의 정원

문어들은 평면 바다 밑바닥 표면에 가장 아름다운 방식으로 자리 잡고 있다. 문어들은 머리가 삼각형의 꼭짓점에 놓이고, 삼각형의 변이 뻗은 촉수로 이루어지도록 바다 밑바닥 평면을 삼각형으로 나누는 배치를 좋아한다. 이런 분할을 삼각분할(triangulation)이라고 부른다. 그래프 이론의 도움을 받아 이 개념을 정식화해 보자.

평면 그래프(planar graph)는 간선끼리 서로 교차하지 않도록 평면 위에 그릴 수 있는 그래프이다.

교차 없이 그려진 그래프의 면(face)은, 그 내부에 간선이나 꼭짓점이 없는 영역을 둘러싸는 단순 사이클이다.

교차 없이 그려진 그래프의 외부 면(outer face)은 넓이가 무한한 영역이다.

평면 위 점 집합의 삼각분할은, 꼭짓점이 이 점들에 놓여 있고 외부 면을 제외한 모든 면이 정확히 세 간선으로 이루어진 퇴화되지 않은 삼각형인, 연결된 평면 그래프이다.

두 삼각형이 공통된 변을 가지면 변으로 연결되어 있다고 한다.

삼각형의 한 변이 외부 면에 닿아 있으면, 그 삼각형과 외부 면은 변으로 연결되어 있다고 한다.

삼각분할의 면들의 집합을 $S$로 나타낸다.

$S$의 원소들이 나열된 수열에서 연속한 두 원소가 변으로 연결되어 있으면, 그 수열을 경로라고 한다.

$S$의 부분집합에서 임의의 두 원소를 골랐을 때, 그 부분집합에 속한 원소만으로 이루어진 경로로 두 원소를 이을 수 있으면, 이 부분집합은 변으로 연결되어 있다고 한다.

삼각분할 $S$가 주어진다.

외부 면을 포함하지 않는 $S$의 부분집합을 생각하자. 다음 두 조건을 만족하면 이 부분집합을 단순 연결이라고 한다.

• 이 부분집합이 변으로 연결되어 있다.
• $S$에서 이 부분집합의 여집합도 변으로 연결되어 있다.

문어들은 단순 연결 집합을 좋아한다. 그 경계를 따라 윤곽 적분을 하려고 하기 때문이다.

삼각분할의 삼각형 하나가 시작 삼각형으로 고정되어 있다.

문어들이 모든 삼각형을 나열한 수열을 찾도록 도와 달라. 수열은 시작 삼각형으로 시작해야 하며, $K$를 삼각형의 개수라고 할 때 모든 $1 \le i \le K$에 대해 삼각형의 집합 $T_{1}$, $T_{2}$, $\ldots$, $T_{i}$가 단순 연결이어야 한다.

첫 줄에 정수 $N$ ($3 \le N \le 100\,000$)과 $M$이 주어진다. 각각 문어의 수와 촉수로 이어진 간선의 수이다. 둘째 줄에는 시작 삼각형의 꼭짓점에 자리한 문어의 번호 $A$, $B$, $C$가 주어진다.

다음 $N$개의 줄에는 문어가 자리한 바다 밑바닥 평면 위 점의 좌표 $X$와 $Y$가 주어진다 ($-10\,000 \le X, Y \le 10\,000$). 모든 점은 서로 다르다.

다음 $M$개의 줄에는 촉수로 간선을 이루는 두 문어의 번호 $U$와 $V$가 주어진다.

문어들은 입력에 나온 순서대로 1번부터 번호가 매겨진다. 문어는 여덟 개가 아니라 몇 개든 촉수를 가질 수 있다.

$S$에서 외부 면을 제외한 모든 원소로 이루어진 부분집합은 변으로 연결되어 있다고 알려져 있다. 이 부분집합의 모든 원소의 합집합은 볼록 다각형을 이룬다.

출력의 첫 줄에는 문어들이 만든 삼각형의 개수 $K$를 출력한다. 이어서 $K-1$개의 줄에 삼각형 $T_{i}$ ($2 \le i \le K$)를 이루는 세 문어의 번호 $P^{(1)}_{i}$, $P^{(2)}_{i}$, $P^{(3)}_{i}$를 출력한다. 모든 $1 \le i \le K$에 대해 삼각형의 집합 $T_{1}$, $T_{2}$, $\ldots$, $T_{i}$는 단순 연결이어야 한다. 해가 여럿이면 그중 아무거나 출력한다.

첫 번째 예시에서:

• 첫 번째 삼각형이 문어 1, 2, 3이고 두 번째 삼각형이 문어 2, 4, 5인 수열은 틀렸다. 조건 중 하나를 만족하지 않기 때문이다. 이 두 삼각형은 변으로 연결되어 있지 않다.
• 첫 번째 삼각형이 문어 1, 2, 3이고 두 번째 삼각형이 문어 2, 3, 5인 수열은 옳다.
• 첫 번째 삼각형이 문어 1, 2, 3, 두 번째 삼각형이 문어 3, 5, 6, 세 번째 삼각형이 문어 2, 4, 5인 수열은 틀렸다. 두 조건을 모두 만족하지 않는다. 이 수열이 만든 집합은 변으로 연결되어 있지 않고, 여집합도 변으로 연결되어 있지 않다.

두 번째 예시는 삼각형이 하나뿐이므로 정수 $K$만 출력한다.