Code Submission Evaluation System Login

Datatähti-valmennus

Joukkueet


Task | Statistics


CSES - Joukkueet

Time limit:1.00 s Memory limit:128 MB

Uolevin luokalla on $n$ oppilasta ja heidän välillään on $m$ kaverisuhdetta. Tehtäväsi on muodostaa oppilaista kaksi joukkuetta niin, että saman joukkueen sisällä kukaan ei ole kaveri toisen kanssa. Voit valita joukkueiden koot haluamallasi tavalla.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $m$: oppilaiden ja kaverisuhteiden määrä. Oppilaat on numeroitu $1,2,\ldots,n$.

Sitten syötteessä on $m$ riviä, joista jokainen kuvaa yhden kaverisuhteen. Rivillä on kaksi kokonaislukua $a$ ja $b$, mikä tarkoittaa, että oppilaat $a$ ja $b$ ovat kavereita.

Oppilas ei voi olla kaveri itsensä kanssa. Lisäksi voit olettaa, että jokainen kaverisuhde esiintyy vain kerran syötteessä.

Tuloste

Tulosta "10-4", jos joukkueet on mahdollista muodostaa, ja muuten "QAQ".

Jos joukkueet voi muodostaa, tulosta lisäksi esimerkki joukkueista. Tulosta jokaisesta oppilaasta "1" tai "2" sen mukaan, kumpaan joukkueeseen oppilas kuuluu. Voit tulostaa minkä tahansa kelvollisen ratkaisun.

Rajat
Esimerkki

Syöte:
5 3
1 2
1 3
4 5


Tuloste:
10-4
1 2 2 1 2