Uolevin luokalla on n oppilasta. Tehtäväsi on muodostaa mahdollisimman monta tanssiparia, kun tiedät, ketkä suostuvat tanssimaan toistensa kanssa. Tanssiparissa on kaksi oppilasta, joista toinen on poika ja toinen on tyttö.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja m: oppilaiden määrä ja sopivien parien määrä. Oppilaat on numeroitu kokonaisluvuin 1,2,\ldots,n.

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

Lopuksi syötteessä on m riviä, jotka kertovat toisilleen sopivat parit. Joka rivillä on kaksi kokonaislukua a_i ja b_i. Tämä tarkoittaa, että a_i ja b_i sopivat toisilleen.

Tuloste

Ohjelmasi tulee tulostaa ensin, mikä on suurin mahdollinen parien määrä. Tämän jälkeen ohjelmasi tulee tulostaa jokainen pari ratkaisussa.

Jos vaihtoehtoja on useita, voit tulostaa minkä tahansa.

Rajat

• 1 \le n \le 100
• 1 \le m \le 1000

Esimerkki

Syöte:

5 4
T T P T P
1 3
2 5
3 4
4 5

Tuloste:

2
1 3
4 5