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

Uolevi perusti vain nörteille tarkoitetun seuranhakupalvelun, josta tuli heti valtava menestys. Palvelusta puuttuu kuitenkin vielä tärkeä toiminto: algoritmi, joka sopii treffit automaattisesti. Sinun täytyy auttaa Uolevia toteuttamaan tämä toiminto.

Tiedossasi on jokaisesta käyttäjästä, sopivatko he toisilleen tietokoneen analyysin perusteella. Lisäksi tiedät, mitä tekstieditoria kukin käyttää (vim tai emacs). Suhteesta tulee pitkäaikainen vain, jos toinen käyttää vimiä ja toinen emacsia, koska silloin heillä riittää loputtomasti keskusteltavaa.

Tehtäväsi on muodostaa mahdollisimman monta paria, jotka sopivat toisilleen ja joissa editorit ovat vastakkaiset. Sama henkilö ei voi kuulua moneen pariin.

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja m: käyttäjien määrä ja sopivien parien määrä. Käyttäjät on numeroitu kokonaisluvuin 1,2,\ldots,n.

Sitten syötteessä on rivi, joka sisältää n merkkiä e_1,e_2,\ldots,e_n: käyttäjien editorit. Jokainen merkki on E (emacs) tai V (vim).

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 200

Esimerkki

Syöte:

5 4
E E V E V
1 3
2 5
1 4
4 5

Tuloste:

2
1 3
4 5