เจ้าชายอีวาน (Ivan Tsarevich) ในระหว่างการตามหาความตายของคอสเชผู้เป็นอมตะ (Koschei the Deathless) ได้เดินทางมาถึงป่าวิเศษแห่งหนึ่ง ตามคำบอกเล่าของแม่มดบาบา ยากา (Baba Yaga) ในป่านี้มีต้นโอ๊กผู้ปราดเปรื่องอยู่ $n$ ต้น ซึ่งในจำนวนนี้มีต้นโอ๊กอยู่ $k$ ต้นพอดีที่พูดความจริงเสมอ ในขณะที่ต้นอื่นๆ พูดโกหกเสมอ

เพื่อที่จะรู้ว่าต้องเดินทางไปที่ใดต่อ เจ้าชายจำเป็นต้องถามเส้นทางต่อไปจากเหล่าต้นโอ๊ก อย่างไรก็ตาม เขาต้องระมัดระวังเป็นอย่างยิ่ง เพราะหากเขาทำตามคำแนะนำของต้นโอ๊กที่พูดโกหก เขาจะหลงเข้าไปในบึงที่เจ้าตาเดียวลีโค (Likho) ดักซุ่มโจมตีอยู่

เพื่อหาว่าต้นโอ๊กต้นใดที่เขาสามารถไว้ใจได้ อีวานจึงได้ถามคำถามแต่ละต้นโอ๊กในรูปแบบนี้: "ต้นโอ๊กหมายเลข $i$ บอกข้าที ต้นโอ๊กหมายเลข $a_i$ พูดความจริงเสมอใช่หรือไม่?" อย่างไรก็ตาม เขาไม่สามารถคิดออกว่าจะสรุปผลจากคำตอบที่ได้รับอย่างไรดี

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

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

บรรทัดแรกมีจำนวนเต็มสองตัวคือ $n$ และ $k$ ($1 \le n \le 5 \cdot 10^5$, $0 \le k \le n$) แทนจำนวนต้นโอ๊กและจำนวนต้นโอ๊กที่พูดความจริงเสมอตามลำดับ

บรรทัดที่ $i$ จาก $n$ บรรทัดถัดไป มีจำนวนเต็มสองตัวคือ $a_i$ และ $b_i$ ($1 \le a_i \le n$, $0 \le b_i \le 1$) แทนการที่ต้นโอ๊กหมายเลข $i$ ถูกถามว่าต้นโอ๊กหมายเลข $a_i$ พูดความจริงเสมอหรือไม่ และคำตอบคือ "ใช่" หาก $b_i = 1$ หรือ "ไม่ใช่" ในกรณีอื่นๆ

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

หากข้อมูลนำเข้าขัดแย้งกันเอง ให้พิมพ์จำนวนเต็มตัวเดียวคือ $-2$

มิฉะนั้น ให้พิมพ์จำนวนเต็ม $n$ ตัว คือ $t_1, t_2, \dots, t_n$ แทนข้อสรุปว่าต้นโอ๊กแต่ละต้นพูดความจริงหรือไม่ ซึ่งสามารถมีค่าได้ดังต่อไปนี้:

• $t_i = 1$ หากต้นโอ๊กหมายเลข $i$ พูดความจริงเสมอ;
• $t_i = -1$ หากต้นโอ๊กหมายเลข $i$ พูดโกหกเสมอ;
• $t_i = 0$ หากเป็นไปไม่ได้ที่จะระบุว่าต้นโอ๊กหมายเลข $i$ พูดโกหกหรือพูดความจริงเสมอจากข้อมูลที่มีอยู่

ตัวอย่าง

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

6 4
2 0
1 0
3 1
3 0
3 0
6 1

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

0 0 -1 1 1 1

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

3 1
2 0
3 0
1 0

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

-2