| Codeforces Round 610 (Div. 2) |
|---|
| Закончено |
Мы заботимся о моральном состоянии участников соревнования. Поэтому вместо задачи мы предлагаем вам полакомиться кусочком торта.
Ох, кто-то уже разрезал торт! Мы просили их дождаться вас, но они не послушали. Если поторопитесь, успеете взять кусочек. Вы, конечно, перед тем, как попробовать торт, задумались, как торт был разрезан.
Известно, что торт изначально представлял собой правильный $$$n$$$-угольник, каждая вершина которого имела уникальный номер от $$$1$$$ до $$$n$$$. Вершины были пронумерованы в некотором произвольном порядке.
Каждый кусок торта — это треугольник. Торт разрезали на $$$n - 2$$$ куска следующим образом: каждый раз проводили один разрез ножом (от вершины до вершины) такой, что от текущего торта отделялся ровно один треугольный кусок, а оставшаяся часть продолжала составлять выпуклый многоугольник. Иными словами, каждый раз выбирали три подряд идущие вершины многоугольника и отрезали соответствующий треугольник.
Возможный процесс разрезания торта представлен на рисунке ниже.
Пример разрезания 6-угольного торта. Вам задан набор получившихся $$$n-2$$$ треугольных кусочков в произвольном порядке. Вершины каждого из кусочков записаны в произвольном порядке — по или против часовой стрелки. Каждый кусочек задается тремя числами — номерами соответствующих ему вершин $$$n$$$-угольного торта.
Например, для ситуации с рисунком выше вам мог быть задан набор кусочков: $$$[3, 6, 5], [5, 2, 4], [5, 4, 6], [6, 3, 1]$$$.
Вас интересуют два вопроса.
- Какая была нумерация вершин $$$n$$$-угольного торта?
- В каком порядке отрезались кусочки?
Формально, вам предстоит найти две перестановки $$$p_1, p_2, \dots, p_n$$$ ($$$1 \le p_i \le n$$$) и $$$q_1, q_2, \dots, q_{n - 2}$$$ ($$$1 \le q_i \le n - 2$$$) такие, что если вершины торта пронумерованы числами $$$p_1, p_2, \dots, p_n$$$ в порядке по или против часовой стрелки, то при отрезании кусков торта в порядке $$$q_1, q_2, \dots, q_{n - 2}$$$ всегда отрезается треугольный кусок так, что оставшаяся часть образует один выпуклый многоугольник.
Например, для рисунка выше искомыми перестановками могли бы быть: $$$p=[2, 4, 6, 1, 3, 5]$$$ (или любой её циклический сдвиг, или её переворот и после этого любой циклический сдвиг) и $$$q=[2, 4, 1, 3]$$$.
Напишите программу, которая по заданным треугольным кусочкам находит любую подходящую пару перестановок $$$p$$$ и $$$q$$$.
Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следуют $$$t$$$ независимых наборов входных данных.
Первая строка каждого набора состоит из одного целого числа $$$n$$$ ($$$3 \le n \le 10^5$$$) — количество вершин в торте.
Далее следуют $$$n - 2$$$ строк, описывающих номера вершин кусков торта: каждая строка состоит из трех различных целых чисел $$$a, b, c$$$ ($$$1 \le a, b, c \le n$$$) — номера вершин куска торта, записанные в произвольном порядке. Сами куски тоже заданы в произвольном порядке.
Гарантируется, что ответ на каждый из тестов существует. Также гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.
Выведите $$$2t$$$ строк — ответы на заданные $$$t$$$ наборов в порядке их записи во входных данных. Каждый ответ должен состоять из $$$2$$$ строк.
В первой строке ответа на набор входных данных выведите $$$n$$$ различных чисел $$$p_1, p_2, \dots, p_n$$$($$$1 \le p_i \le n$$$) — номера вершин торта в порядке по или против часовой стрелки. Просмотр вершин торта можно начать с любой из них.
Во второй строке ответа на набор входных данных выведите $$$n - 2$$$ различных чисел $$$q_1, q_2, \dots, q_{n - 2}$$$($$$1 \le q_i \le n - 2$$$) — порядок отрезания кусков торта. Номер куска торта соответствует его номеру во входных данных.
Если существует несколько ответов, выведите любой. Гарантируется, что ответ на каждый из тестов существует.
3 6 3 6 5 5 2 4 5 4 6 6 3 1 6 2 5 6 2 5 1 4 1 2 1 3 5 3 1 2 3
1 6 4 2 5 3 4 2 3 1 1 4 2 6 5 3 3 4 2 1 1 3 2 1
