1092 : สงครามของนายพล (general)
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 64 megabyte(s)

    เกมออนไลน์ใหม่เพิ่งเปิดตัวขึ้น ในเกมนี้ ผู้เล่นแต่ละคนจะเล่นเป็นนายพลซึ่งมีหน้าที่คุมทหารจำนวนหนึ่ง
    เมื่อเกิดการท้ารบระหว่างผู้เล่นสองคน  ผู้เล่นที่ชนะการสู้รบคือผู้เล่นที่มีทหารจำนวนมากกว่า แต่ถ้าหากทั้งสองฝ่ายมีจำนวนทหารเท่ากัน ผู้เล่นที่ชนะคือผู้เล่นที่มีหมายเลขประจำตัวนายพลที่น้อยกว่า
    ผู้เล่นที่ชนะ จะได้กำลังพลเพิ่มขึ้น ซึ่งเท่ากับทหารจำนวนครึ่งหนึ่งของฝ่ายที่แพ้ (กรณีที่จำนวนทหารหารด้วยสองไม่ลงตัว ให้ปัดเศษทิ้ง)
    ผู้เล่นที่แพ้ จะถูกเปลี่ยนจากสถานะ “นายพล” เป็นสถานะ “เชลย” ของผู้เล่นที่ชนะ  นอกจากนี้ผู้เล่นที่เคยตกเป็นเชลยของฝ่ายแพ้ จะกลายเป็นเชลยของฝั่งผู้ชนะในการแข่งขันด้วย
    บางครั้งนายพลบางคนก็ขี้ขลาด ไม่ยอมท้ารบกับนายพลด้วยกันเอง แต่กลับไปท้ารบกับเชลยของนายพลคนอื่น ในกรณีเหล่านี้ นายพลของเชลยที่ถูกท้ารบนั้นก็มีหน้าที่ต้องปกป้องเชลยของตน และจะต้องต่อสู้แทนเชลยคนนั้น หรือบางครั้งเชลยก็ทะเลาะกันเอง จนทำให้นายพลของเชลยเหล่านี้ต้องมารบกัน ก็เป็นไปได้เช่นเดียวกัน
    คุณเป็นผู้ดูแลระบบเกมออนไลน์นี้ คุณได้รับข้อมูลการปะทะกันระหว่างผู้เล่นแต่ละคู่ หน้าที่ของคุณคือบอกว่าในแต่ละครั้ง ผู้เล่นฝั่งใดเป็นฝ่ายชนะ

งานของคุณ

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

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

    บรรทัดแรกมีจำนวนเต็มสองจำนวน N, M แทนจำนวนนายพลและจำนวนครั้งในการรบ (1≤N,M≤100,000)
    อีก N บรรทัดถัดมาบอกข้อมูลของจำนวนทหารของผู้เล่นแต่ละคนในตอนเริ่มต้น โดยในบรรทัดที่ i+1 มีจำนวนเต็มหนึ่งตัว แสดงจำนวนทหารที่นายพลหมายเลข i มี ผู้เล่นแต่ละคนมีทหารจำนวนไม่เกิน 10,000 นายในตอนเริ่มต้น
    อีก M บรรทัด มีจำนวนเต็มบรรทัดละสองตัวคือ a,b แสดงว่า a และ b ท้ารบกัน (1≤a,b≤N และ a≠b)

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

    มี M บรรทัด แต่ละบรรทัดบอกหมายเลขประจำตัวนายพลของฝั่งผู้ชนะของการรบแต่ละครั้ง ถ้าไม่มีการรบเกิดขึ้น (คนที่ท้ารบกันเป็นเชลยของนายพลคนเดียวกัน) ให้พิมพ์ -1

การให้คะแนน

ชุดข้อมูลทดสอบมูลค่าไม่เกิน 40 คะแนน มีค่า N,M≤1,000 และในทุกชุดข้อมูลทดสอบมีค่า N,M≤100,000

โจทย์โดย: ทักษพร กิตติอัครเสถียร
ที่มา: TOI.C:05-2009

ตัวอย่างข้อมูลนำเข้า	ตัวอย่างข้อมูลส่งออก
5 4 3 4 5 6 7 1 5 1 2 1 2 3 4	5 5 -1 4

ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้