Тек $\texttt{01}$ жолдарын өңдейтін арнайы жол түрлендіру машинасы бар, оның ішінде бірнеше ережеден тұратын ақырлы $\mathcal{R}$ жиыны алдын ала орнатылған. Әрбір ереже $(u, v)$ түрінде болады, мұндағы $u, v$ — ұзындықтары бірдей бос емес $\texttt{01}$ жолдары; бұл бір операция қадамында ағымдағы жолдың $u$ ішкі жолын таңдап, оны $v$ жолына ауыстыруға болатынын білдіреді. Машинаға ұзындықтары бірдей бос емес $(s, t)$ $\texttt{01}$ жолдар жұбы енгізілген сайын, машина $s$ жолын $t$ жолына түрлендіру үшін қажетті ең аз операция қадамдарының санын шығарады немесе шешімі жоқ екенін хабарлайды.

Сіз бұрын осы машинаға ұзындықтары бірдей бос емес $n$ $\texttt{01}$ жолдар жұбын $(s_1, t_1), (s_2, t_2), \dots, (s_n, t_n)$ енгізгеніңізді есіңізге түсірдіңіз. Кездейсоқ сәйкестікпен, сіздің жадыңызда әрбір сұранымның шешімі табылып қана қоймай, ең аз операция қадамдарының саны $d_i \leqslant 2$ шартын да қанағаттандырған.

Жадыңыздың қателеспегенін тексеру үшін келесіні анықтаңыз: машинаның осы $n$ енгізуге беретін нақты нәтижелері сіздің жадыңыздағы мәліметтермен толық сәйкес келетіндей $\mathcal{R}$ ережелер жиыны бар ма?

Кіріс деректер

Бірінші жолда тест жиындарының санын білдіретін бір оң бүтін сан $T$ берілген.

Әрбір тест жиыны үшін бірінші жолда сұраным жазбаларының санын білдіретін бір оң бүтін сан $n$ берілген. Келесі $n$ жолдың $i$-ші жолында ұзындықтары бірдей бос емес екі $\texttt{01}$ жолы $s_i, t_i$ және бір бүтін сан $d_i$ ($0 \leqslant d_i \leqslant 2$) берілген; олар сәйкесінше $i$-ші енгізудегі бастапқы жолды, мақсатты жолды және машина берген ең аз операция қадамдарының санын білдіреді.

Шығыс деректер

Әрбір тест жиыны үшін бір жолға бір сөз шығарыңыз. Егер шарттарды қанағаттандыратын $\mathcal{R}$ ережелер жиыны бар болса, YES деп, әйтпесе NO деп шығарыңыз.

YES және NO сөздерін әріп регистріне қарамастан кез келген түрде шығаруға болады; мысалы, yes, Yes немесе YES бірдей жауап ретінде қабылданады.

Мысалдар

Кіріс деректер 1

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

Шығыс деректер 1

YES
NO
NO

Ескертпе

• $1$-ші тест жиыны: тек бір ғана ережеден тұратын $\mathcal{R} = \{(\texttt{01}, \texttt{10})\}$ жиынын құрастыруға болады:
  • $1$-ші сұраным үшін $s_1 = t_1 = \texttt{010}$, сондықтан түрлендіру ешқандай операциясыз-ақ орындалады, ең аз операция қадамдарының саны $0$-ге тең.
  • $2$-ші сұраным үшін $\texttt{001}$ жолының $\texttt{01}$ суффиксін $\texttt{10}$ жолына ауыстырсақ, $1$ қадам ішінде $\texttt{010}$ алынады.
  • $3$-ші сұраным үшін $\texttt{001}$ мен $\texttt{100}$ жолдары $1$-ші орында да, $3$-ші орында да өзгеше болғандықтан, ұзындығы $2$ болатын ереженің өзімен ғана түрлендіруді $1$ қадамда аяқтау мүмкін емес; бірақ алдымен бастапқы $\texttt{001}$ жолының $\texttt{01}$ суффиксін $\texttt{10}$-ға ауыстырып $\texttt{010}$ аралық жолын алуға, содан кейін $\texttt{010}$ аралық жолының $\texttt{01}$ префиксін $\texttt{10}$-ға ауыстырып $\texttt{100}$ мақсатты жолын алуға болады, сондықтан ең аз операция қадамдарының саны $2$-ге тең.
• $2$-ші тест жиыны: $1$ қадам ішінде $\texttt{10}$ жолын $\texttt{01}$ жолына түрлендіру үшін $\mathcal{R}$ ережелер жиынында міндетті түрде $(\texttt{10}, \texttt{01})$ ережесі болуы керек. Алайда бұл ереже енгізілген сәтте-ақ, $2$-ші сұранымда $\texttt{100}$ жолының $\texttt{10}$ префиксін $\texttt{01}$-ге ауыстыру арқылы $1$ қадамда $\texttt{010}$ алуға болады, ал бұл жадыңыздағы $d_2 = 2$ мәніне қайшы келеді.
• $3$-ші тест жиыны: түрлендіру барысындағы барлық жолдар ұзындықтары бірдей $\texttt{01}$ жолдары болуы тиіс. Ұзындығы $1$-ге тең $\texttt{01}$ жолдарының тек $\texttt{0}$ және $\texttt{1}$ деген екі түрі ғана бар; егер $\texttt{0}$-ден $\texttt{1}$-ге түрлендіру мүмкін болса, онда міндетті түрде $(\texttt{0}, \texttt{1})$ ережесі бар және ол тек $1$ қадамда орындалады, сондықтан ең аз дегенде $2$ қадам қажет болуы мүмкін емес.

Шектеулер

Барлық тест деректері үшін $T \geqslant 1$, $n \geqslant 1$, $0 \leqslant d_i \leqslant 2$, $1 \leqslant |s_i| = |t_i|$ екендігіне және $s_i, t_i$ жолдарының тек $\texttt{0}$ мен $\texttt{1}$ таңбаларынан тұратынына кепілдік беріледі.

Бір тест жиынындағы барлық бастапқы жолдардың ұзындықтарының қосындысын $L = \sum_{i=1}^{n} |s_i|$ деп, ал бір тест файлындағы барлық тест жиындары бойынша $L$ мәндерінің қосындысын $\sum L$ деп белгілесек, $\sum L \leqslant 3\times 10^6$ болатынына кепілдік беріледі.

Бұл есепте ішкі тапсырмалардың орынды тәуелділіктері қосылған.

• A ерекше қасиеті: барлық $1 \leqslant i \leqslant n$ үшін $|s_i| \geqslant 50$ орындалатынына кепілдік беріледі.