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

• 1 \le n \le 10^5
• 1 \le m \le 2 \cdot 10^5
• 1 \le a,b \le n

Esimerkki

Syöte:

5 3
1 2
1 3
4 5

Tuloste:

10-4
1 2 2 1 2