Županijsko natjecanje iz informatike 2017. / Srednja škola / Druga podskupina (3. i 4. razred) - 2. zadatak

Mirko je veliki ljubitelj tenisa te prije svakog turnira pokušava predvidjeti rasplet svih mečeva od prvog kola pa sve do finala.

Svoja predviđanja zapisuje u strukturiranu tablicu koju nazivamo stablo turnira.

Ako se turnir sastoji od n kola, onda na njemu sudjeluje 2 n igrača označenih redom brojevima od jedan na dalje te se stablo turnira sastoji od n + 1 redaka.

U najdonji redak zapisujemo jedan za drugim, slijeva na desno, parove igrača koji međusobno igraju u prvom kolu.

Dakle, u prvom kolu međusobno igraju prvi i drugi po redu igrač iz zadnjeg retka, treći i četvrti, i tako dalje.

U redak iznad zapisujemo redom pobjednike tih mečeva, a parove sljedećeg kola opet čine prvi i drugi igrač u retku, treći i četvrti i tako dalje.

Postupak ponavljamo sve dok ne dođemo do prvog retka u kojem je zapisan pobjednik turnira.

Mirko je iz novima u najdonji redak tablice prepisao ždrijeb prvog kola turnira te prema svojim predviđanjima popunio ostatak stabla naljepnicama s imenima tenisača.

Njegova sestra je, pod okriljem noći, odlijepila sve naljepnice, dobro ih promiješala, i zalijepila nazad na stablo.

Mirko je shvatio da nešto ne valja, ali je nakon početnog šoka odahnuo jer je shvatio da će ipak moći rekonstruirati njegova predviđanja.

Zadano je stablo turnira u kojem zadnji redak odgovara originalnom, dok su ostali elementi možda izmiješani.

Odredite originalno stablo turnira. Možete pretpostaviti da rješenje postoji te da je jedinstveno.

Ulazni podaci

Prvi red sadrži prirodni broj n (1 ≤ n ≤ 10) — broj kola u turniru.

U k-tom od sljedećih n + 1 redova nalazi se 2 k−1 prirodnih brojeva — oznake igrača u k-tom redu stabla turnira slijeva nadesno.

Svaka oznaka igrača je prirodni broj između 1 i 2 n uključivo.

Sve oznake u zadnjem redu su različite.

Izlazni podaci

Ispišite n + 1 redova koji sadržavaju originalno stablo turnira u istom obliku kao na ulazu.

Ispisano stablo mora biti ispravno stablo turnira od kojeg se može dobiti stablo na ulazu postupkom opisanim u tekstu zadatka.

Između ostalog, zadnji red izlaza mora biti potpuno jednak zadnjem redu ulaza.

PRIMJERI TEST PODATAKA

Ulaz

1
1
2 1

Izlaz

1
2 1

Ulaz

3
3
6 2
7 7 7 3
2 5 7 8 1 3 6 4

Izlaz

7
7 3
2 7 3 6
2 5 7 8 1 3 6 4

Ulaz

2
3
2 2
4 3 2 1

Izlaz

2
3 2
4 3 2 1