توجد آلة لتحويل السلاسل النصية مخصصة لمعالجة سلاسل $\texttt{01}$، وقد ضُبطت بداخلها مسبقًا مجموعة منتهية من القواعد $\mathcal{R}$. كل قاعدة تكون على الشكل $(u, v)$، حيث $u, v$ سلسلتان غير فارغتين من نوع $\texttt{01}$ ولهما نفس الطول، مما يعني أنه في خطوة عملية واحدة يمكن اختيار سلسلة فرعية $u$ من السلسلة الحالية واستبدالها بـ $v$. في كل مرة يتم فيها إدخال زوج من سلاسل $\texttt{01}$ غير الفارغة والمتساوية في الطول $(s, t)$ إلى الآلة، تُخرج الآلة أقل عدد من خطوات العمليات اللازمة لتحويل $s$ إلى $t$، أو تُبلغ بعدم وجود حل.

تتذكر أنك أدخلت سابقًا إلى هذه الآلة $n$ من أزواج سلاسل $\texttt{01}$ غير الفارغة والمتساوية في الطول $(s_1, t_1), (s_2, t_2), \dots, (s_n, t_n)$. ومن باب المصادفة، في ذاكرتك، لم يكن لكل استعلام حل فحسب، بل كان يحقق أيضًا أن أقل عدد من خطوات العمليات هو $d_i \leqslant 2$.

للتحقق مما إذا كان هناك خلل في ذاكرتك، يرجى تحديد ما إذا كانت توجد مجموعة قواعد $\mathcal{R}$ تجعل المخرجات الفعلية للآلة لهذه المدخلات الـ $n$ متطابقة تمامًا مع ذاكرتك.

الإدخال

يحتوي السطر الأول على عدد صحيح موجب $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{01}$ في $\texttt{001}$ بـ $\texttt{10}$، نحصل على $\texttt{010}$ في خطوة $1$.
  • بالنسبة للاستعلام رقم $3$، بما أن $\texttt{001}$ و$\texttt{100}$ تختلفان في كلٍّ من الموضع رقم $1$ والموضع رقم $3$، فلا يمكن لقاعدة طولها $2$ وحدها إتمام التحويل في خطوة $1$؛ ولكن يمكن أولًا استبدال اللاحقة $\texttt{01}$ للسلسلة الابتدائية $\texttt{001}$ بـ $\texttt{10}$ للحصول على السلسلة الوسيطة $\texttt{010}$، ثم استبدال البادئة $\texttt{01}$ للسلسلة الوسيطة $\texttt{010}$ بـ $\texttt{10}$ للحصول على السلسلة الهدف $\texttt{100}$، ولذلك فإن أقل عدد من خطوات العمليات هو $2$.
• حالة الاختبار رقم $2$: لكي يتم تحويل $\texttt{10}$ إلى $\texttt{01}$ في خطوة $1$، يجب أن تحتوي مجموعة القواعد $\mathcal{R}$ على القاعدة $(\texttt{10}, \texttt{01})$. غير أنه بمجرد تضمين هذه القاعدة، لن يحتاج الاستعلام رقم $2$ إلا إلى استبدال البادئة $\texttt{10}$ في $\texttt{100}$ بـ $\texttt{01}$ للحصول على $\texttt{010}$ في خطوة $1$، وهو ما يتناقض مع $d_2 = 2$ في ذاكرتك.
• حالة الاختبار رقم $3$: يجب أن تكون جميع السلاسل أثناء عملية التحويل سلاسل $\texttt{01}$ متساوية الطول. لا توجد سوى سلسلتين من نوع $\texttt{01}$ بطول $1$ هما $\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|$ مجموع أطوال جميع السلاسل الابتدائية في حالة اختبار مفردة، وليكن $\sum L$ مجموع قيم $L$ لجميع حالات الاختبار داخل ملف اختبار واحد؛ يُضمن أن $\sum L \leqslant 3\times 10^6$.

تفعّل هذه المسألة تبعيات منطقية بين المهام الفرعية.

• الخاصية الخاصة A: يُضمن أنه لكل $1 \leqslant i \leqslant n$ يتحقق $|s_i| \geqslant 50$.