ปัญหานี้เป็นปัญหาแบบรันสองรอบ (multi-pass problem)

VegiCat และ VegiDog เล่นเกมด้วยป่า (forest) ที่มีจุดยอด $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)$ ซึ่งแทนเส้นเชื่อมไม่มีทิศทางเส้นเดียวกัน

ตัวอย่างนี้แสดงรูปแบบของข้อมูลนำเข้าและข้อมูลส่งออก ผลลัพธ์ของตัวอย่างมีความถูกต้องสำหรับกราฟและการเรียงสับเปลี่ยนที่แสดง อย่างไรก็ตาม การกำหนดค่าในตัวอย่างไม่ได้รับประกันว่าจะเป็นส่วนหนึ่งของกลยุทธ์ที่ใช้ได้ผลกับทุกป่าที่ถูกต้องและทุกการเรียงสับเปลี่ยน