ACM RTK - 2. skupina

Za žužke gre

Mirko je navdušen žužkofil in podpornik pravic otrok. Doma ima terarij z n žužki, oštevilčenimi s števili od 1 do n, toda ne pozna njihovega spola. Kljub temu pa trdi, da so gotovo vsi žužki heteroseksualni. To želi dokazati tako, da en mesec strmi v terarij in si beleži interakcije med žužki.

Natančno opiši postopek, ki sprejme seznam interakcij med žužki in pove, ali obstaja taka razporeditev spolov, da so bile vse interakcije heteroseksualne (torej med žužkoma različnih spolov). Tvoj postopek kot vhodne podatke dobi število žužkov n, število interakcij med njimi m in seznam teh m interakcij — vsaka interakcija je opisana z dvema številoma s_i in t_i, ki povesta, da sta v i-ti interakciji sodelovala žužka s številkama s_i in t_i.

V posamezni interakciji vedno sodelujeta natanko dva žužka in noben žužek ni nikoli v interakciji sam s sabo. Žužki so lahko samo dveh spolov in spola ne spreminjajo med mesecem opazovanja.