On olemassa merkkijonomuunnin, joka käsittelee nimenomaan $\texttt{01}$-merkkijonoja ja jonka sisään on ennalta asetettu äärellinen sääntöjoukko $\mathcal{R}$. Jokainen sääntö on muotoa $(u, v)$, missä $u, v$ ovat yhtä pitkiä epätyhjiä $\texttt{01}$-merkkijonoja; tämä tarkoittaa, että yhdellä operaatioaskeleella voidaan valita nykyisen merkkijonon osamerkkijono $u$ ja korvata se merkkijonolla $v$. Aina kun koneeseen syötetään pari yhtä pitkiä epätyhjiä $\texttt{01}$-merkkijonoja $(s, t)$, kone tulostaa pienimmän mahdollisen operaatioaskelten määrän, jolla $s$ voidaan muuntaa merkkijonoksi $t$, tai ilmoittaa, ettei ratkaisua ole.

Muistat syöttäneesi tähän koneeseen aikoinaan $n$ paria yhtä pitkiä epätyhjiä $\texttt{01}$-merkkijonoja $(s_1, t_1), (s_2, t_2), \dots, (s_n, t_n)$. Sattumalta muistisi mukaan jokaisella kyselyllä ei ainoastaan ollut ratkaisua, vaan lisäksi pienin operaatioaskelten määrä toteutti ehdon $d_i \leqslant 2$.

Varmistaaksesi, pettääkö muistisi, selvitä: onko olemassa sellaista sääntöjoukkoa $\mathcal{R}$, jolla koneen todelliset tulosteet näille $n$ syötteelle vastaavat täysin muistikuvaasi?

Syöte

Ensimmäinen rivi sisältää positiivisen kokonaisluvun $T$, joka ilmoittaa testitapausten lukumäärän.

Kunkin testitapauksen ensimmäinen rivi sisältää positiivisen kokonaisluvun $n$, joka ilmoittaa kyselytietueiden lukumäärän. Seuraavilla $n$ rivillä $i$:s rivi sisältää kaksi yhtä pitkää epätyhjää $\texttt{01}$-merkkijonoa $s_i, t_i$ sekä kokonaisluvun $d_i$ ($0 \leqslant d_i \leqslant 2$), jotka ilmoittavat $i$:nnen syötteen alkumerkkijonon, kohdemerkkijonon sekä koneen antaman pienimmän operaatioaskelten määrän.

Tuloste

Tulosta jokaiselle testitapaukselle omalle rivilleen yksi merkkijono. Jos ehdot täyttävä sääntöjoukko $\mathcal{R}$ on olemassa, tulosta YES; muussa tapauksessa tulosta NO.

Voit tulostaa merkkijonot YES ja NO käyttäen mitä tahansa kirjainkokoa; esimerkiksi yes, Yes ja YES tulkitaan kaikki samaksi vastaukseksi.

Esimerkit

Syöte 1

3
3
010 010 0
001 010 1
001 100 2
2
10 01 1
100 010 2
1
0 1 2

Tuloste 1

YES
NO
NO

Huomautus

• Testitapaus $1$: Voidaan muodostaa vain yhden säännön sisältävä joukko $\mathcal{R} = \{(\texttt{01}, \texttt{10})\}$:
  • Kyselyssä $1$ pätee $s_1 = t_1 = \texttt{010}$, joten muunnos on valmis ilman yhtäkään operaatiota ja pienin operaatioaskelten määrä on $0$.
  • Kyselyssä $2$ korvaamalla merkkijonon $\texttt{001}$ loppuosa $\texttt{01}$ merkkijonolla $\texttt{10}$ saadaan $\texttt{010}$ $1$ askeleella.
  • Kyselyssä $3$, koska $\texttt{001}$ ja $\texttt{100}$ eroavat toisistaan sekä $1$. että $3$. kohdasta, pelkällä pituuden $2$ säännöllä muunnosta ei voida suorittaa $1$ askeleella; voidaan kuitenkin ensin korvata alkumerkkijonon $\texttt{001}$ loppuosa $\texttt{01}$ merkkijonolla $\texttt{10}$, jolloin saadaan välimerkkijono $\texttt{010}$, ja sen jälkeen korvata välimerkkijonon $\texttt{010}$ alkuosa $\texttt{01}$ merkkijonolla $\texttt{10}$, jolloin saadaan kohdemerkkijono $\texttt{100}$, joten pienin operaatioaskelten määrä on $2$.
• Testitapaus $2$: Jotta $\texttt{10}$ voitaisiin muuntaa merkkijonoksi $\texttt{01}$ $1$ askeleella, sääntöjoukon $\mathcal{R}$ on sisällettävä sääntö $(\texttt{10}, \texttt{01})$. Kun tämä sääntö on mukana, kyselyssä $2$ riittää kuitenkin korvata merkkijonon $\texttt{100}$ alkuosa $\texttt{10}$ merkkijonolla $\texttt{01}$, jolloin $\texttt{010}$ saadaan $1$ askeleella, mikä on ristiriidassa muistissasi olevan arvon $d_2 = 2$ kanssa.
• Testitapaus $3$: Kaikkien muunnosprosessin aikaisten merkkijonojen on oltava yhtä pitkiä $\texttt{01}$-merkkijonoja. Pituuden $1$ $\texttt{01}$-merkkijonoja on vain kaksi: $\texttt{0}$ ja $\texttt{1}$. Jos $\texttt{0}$ voidaan muuntaa merkkijonoksi $\texttt{1}$, on välttämättä oltava olemassa sääntö $(\texttt{0}, \texttt{1})$ ja muunnos onnistuu vain $1$ askeleella, joten on mahdotonta, että tarvittaisiin vähintään $2$ askelta.

Rajoitukset

Kaikissa testiaineistoissa taataan, että $T \geqslant 1$, $n \geqslant 1$, $0 \leqslant d_i \leqslant 2$, $1 \leqslant |s_i| = |t_i|$ ja että $s_i, t_i$ ovat merkkijonoja, jotka koostuvat vain merkeistä $\texttt{0}$ ja $\texttt{1}$.

Olkoon $L = \sum_{i=1}^{n} |s_i|$ yhden testitapauksen kaikkien alkumerkkijonojen pituuksien summa ja $\sum L$ yhden testitiedoston kaikkien testitapausten suureiden $L$ summa; taataan, että $\sum L \leqslant 3\times 10^6$.

Tässä tehtävässä on käytössä järkevät osatehtäväriippuvuudet.

• Erikoisominaisuus A: Taataan, että kaikilla $1 \leqslant i \leqslant n$ pätee $|s_i| \geqslant 50$.