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 ลบม/ว

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

อัตราการเปลี่ยนแปลงสุทธิของปริมาตรน้ำของอ่างเก็บน้ำใด ๆ คือผลรวมของน้ำที่เข้าและน้ำที่เสียไปจากท่อที่ติดกับอ่างเก็บน้ำนั้น กล่าวคือ ถ้าอ่างเก็บน้ำติดกับท่อที่น้ำถูกนำออกในอัตรา 2d1, 2d2, ..., 2da ลบม/ว และติดกับท่อที่มีน้ำถูกปั้มเข้ามาในอัตรา 2p1, 2p2, ..., 2pb ลบม/ว แล้ว อัตราการเปลี่ยนแปลงสุทธิของปริมาตรน้ำในอ่างเก็บน้ำนั้นคือ p1+p2+...+pb-d1-d2-...-da

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

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