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 n ja m: osallistujien määrä ja tuttavuuksien määrä. Osallistujat on numeroitu kokonaisluvuin 1,2,\ldots,n.

Sitten syötteessä on rivi, joka sisältää n merkkiä s_1,s_2,\ldots,s_n: osallistujien sukupuolet. Jokainen merkki on T (tyttö) tai P (poika).

Seuraavat m riviä sisältävät toisensa tuntevat osallistujat. Jokaisella rivillä on kaksi kokonaislukua a_i ja b_i. Tämä tarkoittaa, että a_i ja b_i 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

• 4 \leq n \leq 100
• 0 \leq m \leq 500
• 1 \leq a_i, b_i \leq n

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