ישנה מכונה להתמרת מחרוזות המעבדת במיוחד מחרוזות $\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$.