Baltic2013

Ball Machine

เรามีเครื่องจักรลูกบอล (ball machine) ที่สามารถพิจารณาว่าเป็น rooted tree ได้ โหนดใน tree ดังกล่าวจะมีหมายเลขตั้งแต่ 1 ถึง N แต่ละโหนดอาจจะว่างหรือมีลูกบอลหนึ่งลูก เมื่อเริ่มต้น ทุกโหนดอยู่ในสถานะว่าง ขณะที่ทำงาน เครื่องจักรจะสามารถทำงานตามการดำเนินการได้สองแบบ คือ:

แบบที่ 1. เพิ่มลูกบอล k ลูกเข้าใน ball machine: ลูกบอลจะถูกใส่ทีละลูกที่โหนด root ถ้าลูกบอลมีโหนดที่ว่างที่ติดกันด้านล่าง ลูกบอลจะไหลลงไปที่โหนดนั้น ถ้ามีโหนดลูกที่ว่างหลายโหนด ลูกบอลจะเลือกโหนดที่มีโหนดหมายเลขน้อยที่สุดในต้นไม้ย่อยที่มีโหนดนั้นเป็น root

ถ้าลูกบอลไหลลงไปหลาย ๆ ระดับ ลูกบอลจะเลือกโหนดลูกตามเงื่อนไขดังกล่าวในทุก ๆ ระดับ

ตัวอย่างเช่น ถ้าเราใส่ลูกบอลสองลูกลงในเครื่องจักรในรูปด้านล่าง ลูกบอลทั้งสองจะไหลไปที่โหนด 1 และ 3 ลูกบอลลูกแรกจะไหลจากโหนด 4 ไปยังโหนด 3 เนื่องจากโหนด 3 นั้นว่างอยู่และมีโหนด 1 อยู่ในต้นไม้ย่อยของมัน (ที่ประกอบด้วยโหนด 3 และ 1) จากนั้นลูกบอลจะไหลจากโหนด 3 ไปยังโหนด 1 ลูกบอลลูกที่สองจะไหลจากโหนด 4 ไปยังโหนด 3 และหยุดที่ตำแหน่งนั้น

แบบที่ 2. นำลูกบอลออกจากบางโหนด: โหนดนั้นจะเปลี่ยนสถานะเป็นว่าง จากนั้นลูกบอลที่อยู่ด้านบน (ถ้ามี) ก็จะไหลลงมา เมื่อใดที่โหนดพ่อแม่ของโหนดที่ว่างมีลูกบอล ลูกบอลจะไหลลงไปยังโหนดนั้น

ถ้าเรานำลูกบอลออกจากโหนด 5, 7, และ 8 (ตามลำดับดังกล่าว) จากเครื่องจักรในรูปด้านล่าง โหนด 1, 2, และ 3 จะเปลี่ยนสถานะเป็นโหนดว่าง

Input

• บรรทัดแรกระบุจำนวนเต็ม N และ Q แทนจำนวนโหนดและจำนวนการดำเนินการ

• อีก N บรรทัดหลังจากนั้นเป็นข้อมูลอธิบายเครื่องจักร แต่ละบรรทัดจะระบุจำนวนเต็มหนึ่งจำนวน เป็นหมายเลขของโหนด กล่าวคือ ในบรรทัดที่ i ของกลุ่มบรรทัดเหล่านี้จะระบุหมายเลขของโหนดพ่อแม่ของโหนดที่ i, หรือค่า 0 ถ้าโหนด i เห็นโหนด root ของต้นไม้ดังกล่าว

• อีกแต่ละ Q บรรทัดถัดจากนั้นจะมีจำนวนเต็มสองจำนวนที่ระบุการดำเนินการ การดำเนินการแบบที่ 1 จะระบุด้วยบรรทัดในรูปแบบ 1 k โดยที่ k แทนจำนวนของลูกบอลที่จะใส่เข้าไปในเครื่องจักร สำหรับการดำเนินการแบบที่ 2 จะระบุด้วยบรรทัดในรูปแบบ 2 x โดยที่ x แทนหมายเลขของโหนดที่จะนำลูกบอลออก รับประกันว่าการดำเนินการต่าง ๆ นั้นถูกต้อง กล่าวคือ จะไม่มีการเพิ่มลูกบอลมากกว่าจำนวนโหนดว่างในเครื่องและจะไม่มีการนำลูกบอลออกจากโหนดที่ว่าง

Output

สำหรับการดำเนินการประเภทที่ 1 ให้พิมพ์หมายเลขของโหนดสุดท้ายที่ลูกบอลลูกสุดท้ายที่ใส่ไปไปตกอยู่ สำหรับการดำเนินการประเภทที่ 2 ให้พิมพ์จำนวนลูกบอลที่ไหลลงมาหลังจากการนำลูกบอลออกจากโหนดที่ระบุ

ข้อจำกัด

• N,Q <= 100 000
• ในข้อมูลทดสอบที่มีคะแนน 25 คะแนน แต่ละโหนดจะมี 0 หรือ 2 โหนด นอกจากนี้ ทุก ๆ โหนดที่ไม่มีลูกจะมีระยะทางจากโหนด root เท่ากันทั้งหมด
• ในข้อมูลทดสอบที่มีคะแนน 30 คะแนน แต่ละการดำเนินการจะถูกเรียกโดยรับประกันว่าจะไม่มีลูกบอลไหลลงมาหลังจากการดำเนินการที่ 2
• ในข้อมูลทดสอบที่มีคะแนน 40 คะแนน จะมีการทำงานตามดำเนินการประเภทที่ 1 แค่ครั้งเดียว และจะเป็นกิจกรรมแรกเท่านั้น
• เซตของข้อมูลทดสอบทั้ง 3 เซตที่กล่าวมานั้น pairwise disjoint กัน

Pipes

เมือง Hotham ตกเป็นเป้าหมายของการทำลายของ Jester อีกครั้งหนึ่ง คราวนี้ เป้าหมายของ Jester คือระบบจ่ายน้ำ น้ำจืดของเมือง Hotham เก็บอยู่ที่อ่างเก็บน้ำ N แห่ง เชื่อมต่อกันด้วยท่อน้ำ M ท่อ ระบบท่อนี้รับประกันว่ามีเส้นทางอย่างน้อยหนึ่งเส้น (อาจจะประกอบด้วยท่อหลายท่อ) จากอ่างเก็บน้ำหนึ่งไปยังอ่างเก็บน้ำอื่น ๆ นอกจากนี้ทุก ๆ ท่อเชื่อมต่อกับอ่างเก็บน้ำสองแห่งที่แตกต่างกัน และจะมีท่อไม่เกินหนึ่งท่อสำหรับคู่ของอ่างเก็บน้ำใด ๆ

Jester ได้บุกรุกไปยังบางท่อและได้เริ่มนำน้ำออกจากท่อ ด้วยอารมณ์ศิลปินของ Jester เขารับประกันว่าน้ำที่ไหลออกจากท่อใด ๆ จะมีค่าเป็นเลขคู่ (หน่วยเป็นลูกบาศก์เมตรต่อวินาที) ถ้าน้ำไหลออกจากท่อที่เชื่อมระหว่างอ่างเก็บน้ำ u และ v ด้วยอัตรา 2d ลบม/ว แล้ว อ่างเก็บน้ำ u และ v จะเสียน้ำเท่ากันในอัตรา d ลบม/ว