ในกาแล็กซีแห่งหนึ่งอันไกลโพ้น มีดาวที่มีอารยธรรมเจริญก้าวหน้าอยู่ $N$ ดวง หมายเลข $1$ ถึง $N$ ดาวแต่ละดวงดูแลยานอวกาศหนึ่งลำ ยานแต่ละลำอยู่ในสถานะกำลังใช้งานเพื่อเดินทางไปยังดาวอีกดวงหนึ่ง หรืออยู่ในสถานะไม่ได้ใช้งาน หากยานที่ดาว $a$ ดูแลกำลังใช้งานเพื่อเดินทางไปดาว $b$ ยานนั้นจะเดินทางไปกลับระหว่างดาว $a$ และดาว $b$ ซ้ำ ๆ ขณะเดินทางจากดาว $a$ ไปดาว $b$ ผู้โดยสารทั่วไปสามารถขึ้นยานเพื่อเดินทางจาก $a$ ไป $b$ ได้ แต่ขณะเดินทางกลับจากดาว $b$ ไปดาว $a$ ผู้โดยสารทั่วไปไม่สามารถขึ้นยานได้ เนื่องจากข้อจำกัดด้านเชื้อเพลิงหรือการบรรทุกสัมภาระ เป็นต้น หากยานที่ดาว $a$ ดูแลไม่ได้ใช้งาน ยานนั้นจะจอดรออยู่ที่ดาว $a$

ขณะนี้ยานอวกาศทุกลำไม่ได้ใช้งาน และได้กำหนดตารางการเปลี่ยนสถานะของยานในอนาคตไว้แล้ว การเปลี่ยนสถานะมีสองประเภทดังนี้

• เปลี่ยนยานที่ดาว $a$ ดูแล ซึ่งยังไม่ได้ใช้งาน ให้เริ่มใช้งานเพื่อเดินทางไปดาว $b$ โดยจะทำเช่นนี้เฉพาะเมื่อผู้โดยสารทั่วไปไม่สามารถใช้ยานอวกาศเดินทางจากดาว $b$ ไปดาว $a$ ได้
• เปลี่ยนยานที่ดาว $a$ ดูแล ซึ่งกำลังใช้งาน ให้เป็นสถานะไม่ได้ใช้งาน

คนสองคนที่กำลังวางแผนท่องเที่ยวในกาแล็กซีนี้เตรียมคำถามรูปแบบต่อไปนี้ไว้หลายข้อ เพื่อวางแผนนัดพบกัน

• ณ จุดหนึ่งในตารางเวลา หากคนหนึ่งอยู่ที่ดาว $a$ และอีกคนอยู่ที่ดาว $b$ ทั้งสองสามารถใช้ยานอวกาศในฐานะผู้โดยสารทั่วไปเพื่อไปพบกันได้หรือไม่ และหากทำได้ ควรพบกันที่ดาวดวงใดจึงจะใช้ยานอวกาศน้อยครั้งที่สุด กล่าวคือ มีดาว $c$ ที่ผู้โดยสารทั่วไปสามารถเดินทางจากทั้งดาว $a$ และดาว $b$ ไปถึงด้วยยานอวกาศหรือไม่ และหากมี ดาว $c$ ดวงใดทำให้ผลรวมของจำนวนครั้งที่ใช้ยานจาก $a$ ไป $c$ และจาก $b$ ไป $c$ น้อยที่สุด

คุณซึ่งเป็นโปรแกรมเมอร์ฝีมือดีได้รับมอบหมายให้หาคำตอบของคำถามทั้งหมดของทั้งสองคน

งานที่ต้องทำ

เขียนโปรแกรมตอบคำถาม เมื่อได้รับตารางการเปลี่ยนสถานะยานอวกาศในอนาคตและคำถามเรียงตามลำดับเวลา

ข้อมูลนำเข้า

อ่านข้อมูลต่อไปนี้จากอินพุตมาตรฐาน

• บรรทัดแรกมีจำนวนเต็ม $N,Q$ คั่นด้วยช่องว่าง หมายความว่ามีดาว $N$ ดวง และจำนวนการเปลี่ยนสถานะรวมกับจำนวนคำถามเท่ากับ $Q$
• $Q$ บรรทัดถัดมาระบุการเปลี่ยนสถานะและคำถามตามลำดับเวลา บรรทัดที่ $i$ ($1 \le i \le Q$) มีจำนวนเต็มสองหรือสามจำนวนคั่นด้วยช่องว่าง ให้จำนวนเต็มตัวแรกเป็น $T_i$ ซึ่งเป็นกรณีใดกรณีหนึ่งต่อไปนี้

กรณี $T_i=1$

บรรทัดนี้มีจำนวนเต็ม $T_i,A_i,B_i$ แสดงการเปลี่ยนสถานะดังนี้: เริ่มใช้ยานที่ดาว $A_i$ ดูแลเพื่อเดินทางไปดาว $B_i$

รับประกันว่า $1 \le A_i \le N$, $1 \le B_i \le N$, $A_i \ne B_i$ ในขณะนั้นยานที่ดาว $A_i$ ดูแลยังไม่ได้ใช้งาน และผู้โดยสารทั่วไปไม่สามารถใช้ยานอวกาศเดินทางจากดาว $B_i$ ไปดาว $A_i$ ได้

กรณี $T_i=2$

บรรทัดนี้มีจำนวนเต็ม $T_i,A_i$ แสดงการเปลี่ยนสถานะดังนี้: เปลี่ยนยานที่ดาว $A_i$ ดูแลให้ไม่ได้ใช้งาน

รับประกันว่า $1 \le A_i \le N$ และขณะนั้นยานที่ดาว $A_i$ ดูแลกำลังใช้งานอยู่

กรณี $T_i=3$

บรรทัดนี้มีจำนวนเต็ม $T_i,A_i,B_i$ แสดงคำถามดังนี้: หากขณะนั้นคนหนึ่งอยู่ที่ดาว $A_i$ และอีกคนอยู่ที่ดาว $B_i$ ทั้งสองสามารถใช้ยานอวกาศในฐานะผู้โดยสารทั่วไปเพื่อไปพบกันได้หรือไม่ และหากทำได้ ควรพบกันที่ดาวดวงใดจึงจะใช้ยานอวกาศน้อยครั้งที่สุด

รับประกันว่า $1 \le A_i \le N$, $1 \le B_i \le N$, $A_i \ne B_i$

ข้อมูลส่งออก

สำหรับคำถามแต่ละข้อ ให้แสดงคำตอบต่อไปนี้ทางเอาต์พุตมาตรฐานตามลำดับ ข้อละหนึ่งบรรทัด

• หากสามารถพบกันได้ ให้แสดงหมายเลขดาวที่ควรพบกันเพื่อให้จำนวนครั้งที่ใช้ยานอวกาศน้อยที่สุด
• หากไม่สามารถพบกันได้ ให้แสดงจำนวนเต็ม -1

ข้อจำกัด

ข้อมูลนำเข้าทั้งหมดเป็นไปตามเงื่อนไขต่อไปนี้

• $2 \le N \le 1\,000\,000$
• $1 \le Q \le 1\,000\,000$

งานย่อย

งานย่อย 1 [10 คะแนน]

เป็นไปตามเงื่อนไขต่อไปนี้

• $N \le 5\,000$
• $Q \le 5\,000$

งานย่อย 2 [30 คะแนน]

• $T_i \ne 2$ ($1 \le i \le Q$)

งานย่อย 3 [60 คะแนน]

ไม่มีข้อจำกัดเพิ่มเติม

ตัวอย่าง

ข้อมูลนำเข้า 1

6 5
1 2 4
3 2 6
1 4 3
1 6 4
3 2 6

ข้อมูลส่งออก 1

-1
4

หมายเหตุ

ในตัวอย่างนี้ การเปลี่ยนสถานะและคำถามเกิดขึ้นตามลำดับดังนี้

• เริ่มใช้ยานที่ดาว $2$ ดูแลเพื่อเดินทางไปดาว $4$
• หากขณะนี้ทั้งสองคนอยู่ที่ดาว $2$ และดาว $6$ จะไม่สามารถพบกันได้ จึงแสดง -1
• เริ่มใช้ยานที่ดาว $4$ ดูแลเพื่อเดินทางไปดาว $3$
• เริ่มใช้ยานที่ดาว $6$ ดูแลเพื่อเดินทางไปดาว $4$
• หากขณะนี้ทั้งสองคนอยู่ที่ดาว $2$ และดาว $6$ จะสามารถพบกันที่ดาว $3$ หรือดาว $4$ ได้ เพื่อให้จำนวนครั้งที่ใช้ยานน้อยที่สุด ควรพบกันที่ดาว $4$ จึงแสดง 4

ข้อมูลนำเข้า 2

8 36
1 1 2
1 6 5
1 7 8
3 5 6
1 5 4
1 8 1
3 7 2
3 3 8
3 1 8
1 3 2
1 4 1
3 8 5
3 4 3
2 4
3 6 8
1 2 5
3 6 8
2 8
3 1 4
3 6 8
3 6 3
2 3
3 1 2
1 4 3
3 2 6
1 8 3
3 1 7
3 1 6
3 5 4
2 2
2 5
1 3 6
1 2 7
3 1 4
3 1 5
3 6 7

ข้อมูลส่งออก 2

5
2
-1
1
1
2
-1
5
4
-1
5
2
5
3
5
4
3
5
6