נתון לכם גרף לא מכוון המורכב מ-$n$ צמתים ו-$m$ קשתות. הצמתים ממוספרים מאפס: $0, 1, \dots, n - 1$. עליכם לעבד $q$ שאילתות. כל שאילתה מספקת זוג $(u, v)$ ומבקשת מכם למחוק את הקשת $(u, v)$ מהגרף. אם אין קשת כזו בגרף (למשל, אם $u = v$), אל תעשו דבר. לאחר כל שאילתה, הדפיסו האם הגרף קשיר או לא.
קלט
הקלט מכיל מספר מקרי בדיקה. השורה הראשונה מכילה מספר שלם יחיד $t$ ($1 \le t \le 5 \cdot 10^5$), מספר מקרי הבדיקה. אחריה מופיע תיאור מקרי הבדיקה.
השורה הראשונה של כל מקרה בדיקה מכילה שלושה מספרים שלמים $n$, $m$ ו-$q$ ($2 \le n \le 10^6$, $1 \le m, q \le 10^6$): מספר הצמתים, הקשתות והשאילתות, בהתאמה.
כל אחת מ-$m$ השורות הבאות מכילה שני מספרים שלמים $u_i$ ו-$v_i$ ($0 \le u_i, v_i < n$), המייצגים קשת בין $u_i$ ל-$v_i$. אין בגרף לולאות עצמיות ואין קשתות מקבילות.
כל אחת מ-$q$ השורות הבאות מתארת שאילתה. עם זאת, פרמטרי השאילתה $u_j$ ו-$v_j$ אינם ניתנים ישירות. במקום זאת, השורה ה-$j$ מבין שורות אלו מכילה שני מספרים שלמים $a_j$ ו-$b_j$ ($0 \le a_j, b_j < n$). נניח שהתשובה לשאילתה ה-$k$ היא $c_k = 1$ אם הגרף קשיר או $c_k = 0$ אחרת. אזי $u_j$ ו-$v_j$ נוצרים לפי הנוסחאות:
$$u_j = (2^{j-2}c_1 + 2^{j-3}c_2 + \dots + 2^1 c_{j-2} + 2^0 c_{j-1} + a_j) \bmod n,$$
$$v_j = (3^{j-2}c_1 + 3^{j-3}c_2 + \dots + 3^1 c_{j-2} + 3^0 c_{j-1} + b_j) \bmod n.$$
סכום כל ה-$n$, סכום כל ה-$m$, וסכום כל ה-$q$ על פני כל מקרי הבדיקה אינם עולים על $10^6$.
פלט
עבור כל מקרה בדיקה, הדפיסו $q$ שורות עם המספרים השלמים $c_1, \dots, c_q$: התשובות לשאילתות.
דוגמה
קלט לדוגמה 1
2 3 1 2 0 1 0 0 0 1 4 4 4 0 1 1 2 2 3 0 3 0 1 1 3 0 0 2 3
פלט לדוגמה 1
0 0 1 1 0 0
הערה
במקרה הבדיקה הראשון, השאילתות מבקשות למחוק את הקשתות $(0, 0)$ (אינה קיימת) ו-$(0, 1)$.
במקרה הבדיקה השני, השאילתות מבקשות למחוק את הקשתות $(0, 1)$, $(2, 0)$ (אינה קיימת), $(3, 0)$ ו-$(0, 3)$ (כבר נמחקה בפעולה הקודמת).