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).
Minta- és tesztállományok a KöMaL honlapján találhatók a