هذه مسألة متعددة المراحل (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)$، وهي تمثل نفس الحافة غير الموجهة.

يوضح المثال صيغتي الإدخال والإخراج. مخرجات المثال صحيحة بالنسبة للبيانات والتبديلات المعروضة. ومع ذلك، ليس من المضمون أن تكون تعيينات المثال جزءاً من استراتيجية صالحة لكل غابة صالحة ولكل تبديل.