CSES - Istumapaikat
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Tehtäväsi on suunnitella sitsien istumajärjestys. Sitseille osallistuu nn opiskelijaa, joista puolet tulevat Kumpulasta ja puolet Viikistä. Lisäksi tiedetään mm 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 nn ja mm: opiskelijoiden määrä ja tuttavuuksien määrä. Opiskelijat on numeroitu 1,2,,n1,2,\dots,n. Kumpulan opiskelijoilla on pariton numero ja Viikin opiskelijoilla on parillinen numero.

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

Tuloste

Tulosta ensin kokonaisluku kk: 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

  • 2n5002 \le n \le 500
  • 1m10001 \le m \le 1000
  • 1a,bn1 \le a,b \le n

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öä.