S. 6. Egy stadionba egy mérkőzésre n ember érkezik. Tudjuk, hogy ki kivel ellenséges (feltesszük, hogy az ellenségesség kölcsönös). A feladat az, hogy ültessük le az embereket a stadion jobb és bal lelátójára úgy, hogy egy lelátón belül ne legyenek egymással ellenséges emberek, ha pedig ez nem lehetséges, akkor találjunk erre bizonyítékot.

Hogyan nézzen ki egy ilyen bizonyíték? Soroljunk fel páratlan sok embert úgy, hogy mindenki ellenséges a sorban előtte állóval és utána következővel, és az utolsó is ellenséges az elsővel. (Ezeket az embereket tényleg nem tudjuk megfelelően kettéosztani a két lelátóra.)

A programunk az adatokat a standard bemenetről olvassa. Az emberek sorszámozva vannak 1-től n-ig. A bemenet első sora az emberek n száma, az ezután következő sorokban két-két sorszám, -- két egymással ellenséges ember sorszáma -- található.

Ha sikerül szétültetni az embereket, akkor a standard kimenetre írt eredmény legyen azon emberek sorszáma, akik a bal oldalon üljenek (az 1. embernek a bal oldalon kell ülnie). Ha nem sikerül a szétültetés, akkor a standard kimenetre írjuk ki a fent említett bizonyítékot (a páratlan sok ember sorszámát).

Feltételezhetjük, hogy n értéke legfeljebb 65000, és egy ember legfeljebb 200 másikkal ellenséges.

Figyeljünk a versenykiírásban előírt formátumra! A használt algoritmust le kell írni (vagy külön, vagy a programban kommentekben). Programot csak Pascal, C, C++ és Java nyelven lehet beadni.

Tesztadatok:

picik (5KB),
kicsik (14 KB),
normálisak (839KB),
nagyok (2,9MB),
óriásiak (25MB).

A programnak a

cat pici.3 | program > eredm_pici.3

illetve DOS ablakban:

type pici.3 | program > eredm_pici.3

utasítás hatására kell futnia. Az eredm_pici.3 file tartalma:

1
3
4
5

illetve:

cat pici.4 | program > eredm_pici.4

esetén az eredm_pici.4 file tartalma:

2
1
6

Futási idő, memóriahasználat

Az idők 2 Gigahertzes processzorra vonatkoznak. Az elvárt oszlopokban azt látjuk, hogy mennyi időben/memóriával lehet kényelmesen (semmi ravaszság a programban) megoldani a feladatot, a maximum oszlopokban pedig azt, hogy teszteléskor mennyi memóriát adunk, illetve mennyi ideig várunk az eredményre. Az egyes sorokban a kategóriához tartozó teszteken elért maximum van!