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