Code Submission Evaluation System Login

Datatähti-valmennus

CSES - Datatähti-valmennus - Joukkueet

Joukkueet


View task | Model solution | Statistics


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.

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