JHIO 2022. 1. zadatak

Na izboru za najbolji kulen Europe sudjeluje N malih obiteljskih gospodarstava (OPG) označenih brojevima od jedan do N. Nakon predstavljanja i degustacije kulena, pristupa se glasanju. Svaki OPG-e rangira preostalih N-1 OPG-ova na način da najboljem kulenu po njihovom izboru dodijeli N-1 bodova, donajboljem N-2 bodova i tako sve do zadnjeg kojem dodjeljuje samo jedan bod.

Pitanje #1: Odredi i ispiši oznake OPG-ova čiji su kuleni zauzeli prvo, drugo i treće mjesto. Ako više kulena ima isti broj bodova, prednost ima onaj s manjom oznakom.

Međutim, europski povjerenik za kulen, izvjesni K.M. iz Zagreba, dodatno pregledava ishod glasanja. Naime, Europa ne voli kada OPG-ovi razmjenjuju bodove, tj. kada OPG A da X bodova OPG-u B, a OPG B da X bodova OPG-u A. Kada povjerenik otkrije takvu situaciju, glasovi OPG-a A i OPG-a B se brišu i ne broje se u određivanju nove liste najboljih kulena. Njihovi kuleni ostaju na listi, samo se njihovi glasovi brišu.

Pitanje #2: Odredi i ispiši oznake OPG-ova čiji su kuleni zauzeli prvo, drugo i treće mjesto nakon brisanja bodova OPG-ova koji su razmjenjivali bodove. Ako više kulena ima isti broj bodova, prednost ima onaj s manjom oznakom.

Ulazni podaci

U prvom je retku prirodan broj N (3 ≤ N ≤ 1000), broj iz teksta zadatka

U i-tom od sljedećih N redaka je N-1 prirodnih brojeva Kj (1 ≤ Kj ≤ N-1, Kj ≠ i), oznake kulena onim redom kako ih je OPG oznake i rangirao.

Izlazni podaci

U prvi redak ispiši tražene tri oznake OPG-ova, odgovor na prvo pitanje iz teksta zadatka.

U drugi redak ispiši tražene tri oznake OPG-ova, odgovor na drugo pitanje iz teksta zadatka.

Probni primjeri

Ulaz

3
3 2
3 1
2 1

Izlaz

3 2 1
1 2 3

Opis prvog probnog primjera: OPG 1 osvojio je dva boda, OPG 2 tri boda i OPG 3 četiri boda. OPG 1 dao je OPG-u 2 jedan bod, isto koliko je i OPG 2 dao njemu. Isto tako je OPG 2 dao OPG-u 3 dva boda, koliko i OPG 3 njemu. Zbog toga su obrisani bodovi koje su dodijelila sva tri OPG-a i nakon toga svi OPG-ovi imaju nula bodova pa je, zbog pravila o u slučaju dijeljenja bodova, poredak 1, 2, 3.

Ulaz

4
2 3 4
3 4 1
2 4 1
2 1 3

Izlaz

2 3 4
2 3 1

Ulaz

5
5 3 2 4
1 4 5 3
4 2 5 1
3 5 2 1
1 4 3 2

Izlaz

4 5 1
1 4 5