34340번 - Apollonian Embedding 스페셜 저지

문제

볼록 $N$각형이 주어진다. 각 정점들의 번호는 시계방향으로 1,2,ドル\cdots ,N$이다. $i$번 정점과 $i+1$번 정점 사이에는 양방향 간선이 존재한다 ($N+1$번 정점은 1ドル$번 정점으로 간주한다). 여기에 서로 교차하지 않는 $N-3$개 간선이 새로 주어진다. Apollonian network는 삼각형 그래프에서 시작해 재귀적으로 하나의 삼각형을 작은 3개의 삼각형으로 분할하는 것을 반복해서 만들 수 있는 그래프이다. 자세히는 다음과 같이 생성된다. 처음에는 정점 3개, 간선 3개로 이루어진 그래프로 시작한다. 이때 삼각형 면은 시작 정점 3개로 이루어진 삼각형 1개 뿐이다. 다음 시행을 0ドル$회 이상 반복해서 만들 수 있는 그래프를 Apollonian network라고 부른다.

• 정점 $u,v,w$로 구성된 삼각형 면을 고른다.
• 새로운 정점 $x$를 추가한다.
• 새로운 간선 $xu,ドル $xv,ドル $xw$를 추가한다.
• 삼각형 면 $uvw$를 제거하고 새로운 삼각형 면 3개 $xuv,ドル $xvw,ドル $xwu$를 추가한다.

주어진 그래프를 부분 그래프로 가지며 정점이 $N$개인 Apollonian network를 만들어야 한다. 가능한 방법이 여러 가지라면 아무것이나 출력해도 된다.

입력

첫 번째 줄에는 $N$이 주어진다. (3ドル \leq N \leq 3000$)

이어지는 $N-3$개의 줄에는 대각선을 이루는 정점을 나타내는 두 정수 $u,ドル $v$가 주어진다. (1ドル \leq u < v \leq N$)

출력

Apollonian network를 위의 생성 과정을 따라서 생성한다.

첫 번째 줄에 Apollonian network의 시작 삼각형을 이루는 세 정점을 공백을 사이에 두고 출력한다.

다음 $N-3$개의 줄에는 제거하는 삼각형 면을 이루는 정점 3개 $u,ドル $v,ドル $w$와 추가하는 정점 $x$를 공백을 사이에 두고 출력한다. 각 줄에서 $u, v, w$의 출력 순서는 상관이 없다. 정점이 $N$개인 Apollonian network를 만들기 위해서는 시행을 $N-3$번 해야 됨을 알 수 있다.

제한

힌트