- Time limit: 1.00 s
- Memory limit: 512 MB
Uolevi on tänä vuonna osakuntansa sitsivastaava, ja yksi hänen lukuisista tehtävistään on päättää sitsien istumajärjestys.
Uolevin osakunnan sitsiperinne on seuraavanlainen: Jokainen osallistuja luokittelee itsensä joko tytöksi tai pojaksi. Ihanteellisessa istumajärjestyksessä osallistujat jaetaan pyöreiden pöytien ympärille siten, että vierekkäin istuu aina vuorotellen tyttö ja poika ja jokaisessa pöydässä istuu vähintään 4 ihmistä. Lisäksi vierekkäin istuvien on tunnettava toisensa etukäteen.
Tehtäväsi on selvittää, onko ihanteellinen istumajärjestys mahdollinen, ja jos se on mahdollinen, esittää jokin sellainen järjestys.
Syöte
Syötteen ensimmäisellä rivillä on kaksi kokonaislukua ja : osallistujien määrä ja tuttavuuksien määrä. Osallistujat on numeroitu kokonaisluvuin .
Sitten syötteessä on rivi, joka sisältää merkkiä : osallistujien sukupuolet. Jokainen merkki on T (tyttö) tai P (poika).
Seuraavat riviä sisältävät toisensa tuntevat osallistujat. Jokaisella rivillä on kaksi kokonaislukua ja . Tämä tarkoittaa, että ja tuntevat toisensa.
Tuloste
Mikäli ihanteellinen istumajärjestys ei ole mahdollinen, tulosta ainoastaan merkkijono QAQ.
Muussa tapauksessa tulosta ensimmäiselle riville pöytien lukumäärä, ja sen jälkeen jokaista pöytää kohti ensin pöydässä istuvien lukumäärä, ja sitten järjestyksessä pöydässä istuvat osallistujat.
Rajat
Esimerkki
Syöte:
10 16 T P P T P T P P T T 1 3 1 4 1 6 1 7 2 4 2 6 2 8 3 10 4 5 5 9 5 3 6 8 7 1 7 10 7 9 8 9
Tuloste:
2 4 1 3 10 7 6 4 5 9 8 6 2