Grupa studenata se okupila na letnjem kampu. Svako je znao nekoliko drugih studenata. Ispostavilo se da se svaki par studenata poznaje posredno (preko niza zajedničkih poznanika).
Potrebno je da se studenti podele u dve grupe, ali pošto svako želi da upozna što više novih kolega, potrebno je da svaku grupu čine međusobno nepoznate osobe (dve osobe koje se već poznaju ne mogu biti u istoj grupi). Napisati program koji određuje da li je to moguće i ako jeste, koji će sve studenti biti u grupi sa studentom čiji je redni broj 0.
Sa standardnog ulaza se učitava broj studenata \(n\) (\(1 \leq n \leq 10^5\)), broj parova \(m\) studenata koji se od ranije poznaju (\(0 \leq m \leq \frac{n(n-1)}{2}\)), a zatim i niz parova brojeva od \(0\) do \(n-1\) koji predstavljaju njihova poznanstva.
Na standardni izlaz ispisati redne brojeve studenata koji su u grupi sa studentom koji nosi redni broj 0, u rastućem poretku, ili simbol - ako tražene dve grupe nije moguće formirati.
6 6 0 1 1 2 2 3 3 4 4 5 5 0
0 2 4
Ako su u jednoj grupi studenti sa brojevima \(0\), \(2\) i \(4\), u drugoj su studenti sa brojevima \(1\), \(3\) i \(5\) i tada se ni u jednoj grupi ne nalaze studenti koji se međusobno poznaju.
5 5 0 1 1 2 2 3 3 4 4 0
-
Student \(0\) ne sme da bude u grupi sa studentom \(1\), koji ne sme da bude u grupi sa studentom \(2\), što znači da \(0\) i \(2\) moraju da budu u istoj grupi. Studenti \(2\) i \(3\) ne mogu da budu u istoj grupi, pa su \(1\) i \(3\) u istoj grupi. Student \(4\) ne sme da bude u grupi sa studentom \(3\), pa on mora biti u grupi sa studentima \(0\) i \(2\), međutim, to nije dopušteno, jer se studenti \(4\) i \(0\) poznaju.