Zadanie

Grafová úlohy

Počet bodov: 60

Rozprávka k tejto úlohe bola v kontakte s pozitívnou rozprávkou, preto je v karanténe.

Úloha

Na vstupe je graf, ale nie taký obyčajný graf. Každý vrchol má presne troch susedov. Vašou úlohou bude v tomto grafe nájsť cyklus, ale nie hocijaký cyklus! Chceli by sme taký cyklus, v ktorom sa dá nájsť dvojica vrcholov a, b, ktoré nie sú v cykle susedné, ale existuje medzi nimi hrana H.

Vstup a Výstup

V prvom riadku vstupu je číslo \(n\) – počet vrcholov.

Nasleduje \(n\) riadkov. Na \(i\)-tom z nich sú 3 čísla – traja susedia vrcholu \(i\). Vrcholy majú čísla od \(0\) po \(n-1\).

Vypíšte 1 riadok a na ňom niekľko medzerou oddelených čísel vrcholov, pri čom platí, že každé dva po sebe idúce vrcholy, sú susedné. Navyše nech platí, že druhý a posledný sú tiež susedné a nech sa prvý vrchol v zozname nachádza dva krát. Hranu H, ktorú hľadáme, teda vypíšte ako prvú a následne vypíšte od druhého z vrcholov celý cyklus.

Sú dve sady vstupov. V prvej platí \(10 \leq n \leq 10\,000\). V druhej platí \(10 \leq n \leq 100\,000\).

Príklad

Input:

6
1 2 3
0 2 4
0 1 5
0 4 5
1 3 5
2 3 4

Output:

0 1 4 3 0 2

V tomto grafe existuje veľa správnych riešení.