Code Submission Evaluation System Login

Algoritmit ongelmanratkaisussa 2019

Istumapaikat


Task | Statistics


CSES - IstumapaikatCSES - Istumapaikat

Time limit:1.00 s Memory limit:512 MB

Tehtäväsi on suunnitella sitsien istumajärjestys. Sitseille osallistuu $n$ opiskelijaa, joista puolet tulevat Kumpulasta ja puolet Viikistä. Lisäksi tiedetään $m$ paria opiskelijoita, jotka tuntevat toisensa.

Sitsien osallistujat tulee sijoittaa pyöreisiin pöytiin, joissa jokaisessa on ainakin neljä henkilöä. Vaatimuksena on, että aina kun vierekkäin on kaksi opiskelijaa, he tulevat eri kampuksista ja lisäksi tuntevat toisensa.

Suunnittele jokin mahdollinen tapa muodostaa pöydät tai ilmoita, ettei mitään ratkaisua ole olemassa. Saat valita pöytien määrän ja koot haluamallasi tavalla.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua $n$ ja $m$: opiskelijoiden määrä ja tuttavuuksien määrä. Opiskelijat on numeroitu $1,2,\dots,n$. Kumpulan opiskelijoilla on pariton numero ja Viikin opiskelijoilla on parillinen numero.

Tämän jälkeen syötteessä on $m$ riviä, joista jokainen kuvaa yhden tuttavuuden. Rivillä on kaksi kokonaislukua $a$ ja $b$: Kumpulan opiskelija $a$ ja Viikin opiskelija $b$ tuntevat toisensa. Jokainen tuttavuus annetaan vain kerran.

Tuloste

Tulosta ensin kokonaisluku $k$: pöytien määrä. Tulosta sitten jokaisessa pöydässä istujat esimerkin mukaisesti, järjestyksessä pöydän ympäri jostakin osallistujasta alkaen. Voit tulostaa minkä tahansa kelvollisen ratkaisun.

Jos mitään ratkaisua ei ole olemassa, tulosta vain "IMPOSSIBLE".

Rajat
Esimerkki

Syöte:
10 14
1 4
1 6
1 8
3 2
3 4
5 2
5 6
5 10
7 2
7 6
7 8
7 10
9 4
9 10


Tuloste:
2
4
1 6 7 8
6
2 3 4 9 10 5


Selitys: Muodostetaan kaksi pöytää, joista ensimmäisessä on neljä henkilöä ja toisessa on kuusi henkilöä.