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 nn ja mm: käyttäjien määrä ja sopivien parien määrä. Käyttäjät on numeroitu kokonaisluvuin 1,2,,n1,2,\ldots,n.

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

Lopuksi syötteessä on mm riviä, jotka kertovat toisilleen sopivat parit. Joka rivillä on kaksi kokonaislukua aia_i ja bib_i. Tämä tarkoittaa, että aia_i ja bib_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

  • 1n1001 \le n \le 100
  • 1m2001 \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