זוהי בעיה דו-שלבית (multi-pass).

VegiCat ו-VegiDog משחקים משחק עם יער בן $n$ צמתים, הממוספרים מ-$1$ עד $n$, ו-$m$ קשתות. יער הוא גרף לא מכוון ללא מעגלים. הוא לא בהכרח קשיר.

בשלב הראשון, VegiCat מקצה מספר שלם $a_u$ ($1 \le a_u \le 2n$) לכל צומת $u$. הערכים עשויים לחזור על עצמם.

לאחר ש-VegiCat מסיים להקצות את הערכים, הצמתים ממוספרים מחדש. תהא $p_1, p_2, \ldots, p_n$ תמורה של $1, 2, \ldots, n$, שבה כל מספר שלם מ-$1$ עד $n$ מופיע בדיוק פעם אחת. עבור כל $u$, הצומת שמספרו המקורי היה $u$ ממוספר כעת כ-$p_u$.

כל קשת $(u, v)$ הופכת ל-$(p_u, p_v)$. כל צומת שומר על הערך שהוקצה לו. יהא $b_i$ הערך בצומת $i$ לאחר המספור מחדש. אזי $b_{p_u} = a_u$.

בשלב השני, VegiDog מקבל רק את $n$ ואת $b_1, b_2, \ldots, b_n$, ללא היער המקורי או התמורה $p$. עליו לשחזר את כל הקשתות באמצעות מספרי הצמתים החדשים.

תכננו אסטרטגיות עבור שני השחקנים שיעבדו עבור כל יער חוקי וכל תמורה $p$.

קלט

התוכנית שלכם תרוץ פעמיים: תחילה בתור VegiCat, ולאחר מכן בתור VegiDog. מקרי הבדיקה מופיעים באותו סדר בשתי ההרצות.

הרצה ראשונה. השורה הראשונה מכילה את המחרוזת cat, המציינת שאתם משחקים בתור VegiCat.

השורה השנייה מכילה מספר שלם $T$ ($1 \le T \le 10^4$), מספר מקרי הבדיקה. אחריה מופיע תיאור מקרי הבדיקה.

השורה הראשונה של כל מקרה בדיקה מכילה שני מספרים שלמים $n$ ו-$m$ ($1 \le n \le 2 \cdot 10^5$, $0 \le m < n$), מספר הצמתים והקשתות.

כל אחת מ-$m$ השורות הבאות מכילה שני מספרים שלמים $u$ ו-$v$ ($1 \le u, v \le n$, $u \ne v$), המתארים קשת לא מכוונת בין הצמתים $u$ ו-$v$.

מובטח כי בגרף אין מעגלים או קשתות כפולות.

מובטח כי סכום ערכי $n$ על פני כל מקרי הבדיקה אינו עולה על $2 \cdot 10^5$.

הרצה שנייה. השורה הראשונה מכילה את המחרוזת dog, המציינת שאתם משחקים בתור VegiDog.

השורה השנייה מכילה מספר שלם $T$ ($1 \le T \le 10^4$), מספר מקרי הבדיקה. אחריה מופיע תיאור מקרי הבדיקה.

השורה הראשונה של כל מקרה בדיקה מכילה מספר שלם $n$ ($1 \le n \le 2 \cdot 10^5$), מספר הצמתים.

השורה השנייה מכילה $n$ מספרים שלמים $b_1, b_2, \ldots, b_n$ ($1 \le b_i \le 2n$), הערכים שהוקצו לפי סדר הצמתים החדש.

מובטח כי סכום ערכי $n$ על פני כל מקרי הבדיקה אינו עולה על $2 \cdot 10^5$.

פלט

הרצה ראשונה. עבור כל מקרה בדיקה, הדפיסו $n$ מספרים שלמים $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 2n$) בשורה אחת. המספר השלם $a_i$ הוא הערך שהוקצה לצומת $i$.

הרצה שנייה. עבור כל מקרה בדיקה, הדפיסו בשורה הראשונה מספר שלם $m$, מספר הקשתות. כל אחת מ-$m$ השורות הבאות חייבת להכיל שני מספרים שלמים $u$ ו-$v$ ($1 \le u, v \le n$, $u \ne v$), המתארים קשת באמצעות מספרי הצמתים החדשים.

הדפיסו כל קשת פעם אחת, בכל סדר שהוא. כל אחד משני הקצוות יכול להופיע ראשון. אם $m = 0$, הדפיסו רק $0$.

דוגמאות

קלט 1

cat
4
1 0
4 3
1 2
4 3
2 3
7 2
6 4
7 1
10 7
10 9
7 9
10 5
4 8
3 7
4 10
1 2

פלט 1

1
2 5 8 5
11 11 4 11 3 7 2
10 13 12 5 3 2 16 6 19 3

קלט 2

dog
4
1
1
4
5 2 5 8
7
11 7 2 11 11 3 4
10
16 3 13 5 10 12 19 6 2 3

פלט 2

0
3
1 4
2 1
4 3
2
4 3
5 2
7
1 7
4 8
5 3
6 1
7 10
10 2
10 4

הערה

במקרה הבדיקה הראשון, ליער יש צומת אחד ואין בו קשתות. VegiCat מקצה לצומת את הערך $1$, ו-VegiDog מדפיס $0$.

במקרה הבדיקה האחרון, התמורה היא $p = [5, 3, 6, 4, 2, 9, 1, 8, 7, 10]$.

VegiCat מקצה $a_7 = 16$. מאחר ש-$p_7 = 1$, VegiDog מקבל $b_1 = 16$.

הקשת המקורית $(3, 7)$ הופכת ל-$(p_3, p_7) = (6, 1)$.

הקשת המקורית $(4, 10)$ הופכת ל-$(p_4, p_{10}) = (4, 10)$. הדוגמה מדפיסה קשת זו בתור $(10, 4)$, המייצגת את אותה קשת לא מכוונת.

הדוגמה ממחישה את תבניות הקלט והפלט. הפלטים שלה נכונים עבור הגרפים והתמורות המוצגים. עם זאת, לא מובטח כי ההקצאות שבדוגמה הן חלק מאסטרטגיה שעובדת עבור כל יער חוקי וכל תמורה.