$$ \newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor} \newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil} \renewcommand{\mod}{\,\mathrm{mod}\,} \renewcommand{\div}{\,\mathrm{div}\,} \newcommand{\metar}{\,\mathrm{m}} \newcommand{\cm}{\,\mathrm{cm}} \newcommand{\dm}{\,\mathrm{dm}} \newcommand{\litar}{\,\mathrm{l}} \newcommand{\km}{\,\mathrm{km}} \newcommand{\s}{\,\mathrm{s}} \newcommand{\h}{\,\mathrm{h}} \newcommand{\minut}{\,\mathrm{min}} \newcommand{\kmh}{\,\mathrm{\frac{km}{h}}} \newcommand{\ms}{\,\mathrm{\frac{m}{s}}} \newcommand{\mss}{\,\mathrm{\frac{m}{s^2}}} \newcommand{\mmin}{\,\mathrm{\frac{m}{min}}} \newcommand{\smin}{\,\mathrm{\frac{s}{min}}} $$

Prijavi problem


Obeleži sve kategorije koje odgovaraju problemu

Još detalja - opišite nam problem


Uspešno ste prijavili problem!
Status problema i sve dodatne informacije možete pratiti klikom na link.
Nažalost nismo trenutno u mogućnosti da obradimo vaš zahtev.
Molimo vas da pokušate kasnije.

Да ли је бипартитан

vreme memorija ulaz izlaz
0,1 s 64 Mb standardni izlaz standardni ulaz

Пера je отишао на летњи спортски камп и када је тамо дошао видео је још неколико својих другара. И друга деца су знала понеког. Интересантно, Пера је свако дете знао посредно (знао је некога, ко зна некога, ко зна некога итд. ко зна то дете).

Потребно је да се деца поделе у две групе, али пошто свако жели да упозна што више нових другара, потребно је да сваку групу чине међусобно непознате особе (две особе које се већ познају не могу бити у истој групи). Написати програм који одређује да ли је то могуће и ако јесте, која ће све деца бити у групи са Пером.

Улаз

Са стандардног улаза се учитава број деце \(n\) (\(1 \leq n \leq 10^5\)), а затим и број парова \(m\) деце која се већ познају (\(0 \leq m \leq \frac{n(n-1)}{2}\)), а затим и низ парова бројева од \(0\) до \(n-1\) који представљају познанства.

Излаз

На стандардни излаз исписати редне бројеве деце који су у групи са Пером (кренувши од Пере који има редни број 0, па у растуће поретку) или симбол - ако тражене две групе није могуће формирати.

Пример 1

Улаз

6 6 0 1 1 2 2 3 3 4 4 5 5 0

Излаз

0 2 4

Објашњење

Ако су у једној групи деца са бројевима 0, 2 и 4, у другој су деца са бројевима 1, 3 и 5 и тада се ни у једној групи не налазе деца која се међусобно познају.

Пример 2

Улаз

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

Излаз

-

Објашњење

Пера (особа 0) не сме да буде у групи са особом 1, која не сме да буде у групи са особом 2, што значи да 0 и 2 морају да буду у истој групи. Особе 2 и 3 не могу да буду у истој групи, па су 1 и 3 у истој групи. Особа 4 не сме да буде у групи са особом 3, па она мора бити у групи са особама 0 и 2, међутим, то није допуштено, јер се особе 4 и 0 познају.

Morate biti ulogovani kako biste poslali zadatak na evaluaciju.