Задача №114815. Магический фокус
Артём пришёл в цирк, и сейчас ему предстоит принять участие в фокусе.
Артём загадывает перестановку — массив из \(n\) различных целых чисел от \(1\) до \(n\). Пусть он загадал перестановку \([a_1, a_2, \ldots, a_n]\). Для каждого \(i\) от \(1\) до \(n\) он рассматривает набор чисел \(\{a_i, a_{i+1}, a_{i+2}\}\) (будем считать, что \(a_{n+1} = a_1\), \(a_{n+2} = a_2\)).
Числа в каждом наборе он перемешивает произвольным образом, а затем перемешивает и сами наборы. После чего сообщает получившиеся тройки Иллюзионисту.
Вы — Иллюзионист, угадайте перестановку, которую загадал Артём.
Первая строка содержит целое число \(n\) (\(3 \le n \le 200\,000\)) — количество элементов в перестановке.
Каждая из следующих \(n\) строк содержит три различных целых числа \(a_{i,1}, a_{i,2}, a_{i,3}\) (\(1 \le a_{i,j} \le n\)) — наборы, которые Артём сообщил Иллюзионисту.
Гарантируется, что данные Артёма соответствуют хотя бы одной перестановке.
Выведите перестановку из \(n\) элементов, которую загадал Артём.
Если однозначно восстановить перестановку нельзя, выведите произвольную подходящую перестановку.
Во втором примере подойдёт произвольная перестановка чисел \(1\), \(2\) и \(3\).
6 3 4 1 5 1 6 5 4 2 2 4 3 2 5 6 6 1 3
1 3 4 2 5 6
3 1 2 3 2 3 1 1 2 3
1 2 3