2000 : Mobiles
Problem type : Batch
Time limit : 1.0 second(s)
Memory limit : 32 megabyte(s)
คุณถูกขอร้องให้ซื้อของขวัญให้กับลูกของพี่ชายชื่อ ไอค์ อย่างไรก็ตามคุณสังเกตเห็นว่า ไอค์มีรสนิยมเฉพาะในเรื่องของขวัญกล่าวคือไอค์ชอบเฉพาะทุกๆอย่างที่ไอค์สามารถจัดเรียงลำดับได้

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



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

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

ในตัวอย่างรูปด้านบน ไอค์ ไม่ชอบ โมบายแบบนี้ แม้ว่ามันจะสอดคล้องเงื่อนไขที่ 1 แต่ไม่เข้าเงื่อนไขข้อที่ 2 เนื่องจากของเล่นที่ปลายด้านซ้ายสุดอยู่สูงกว่าของเล่นที่อยู่ทางด้านขวามือ

อย่างไรก็ตาม โมบายนี้สามารถปรับเปลี่ยนให้เป็นแบบที่ ไอค์ ชอบได้ โดยการสลับที่เป็นไปตาม
  1. ขั้นแรก ปลายทางด้านซ้ายและขวาของแกนสลับที่กันซึ่งเป็นผลให้แกนหมายเลข 2 และแกนหมายเลข 3 เปลี่ยนที่กันดังแสดงไว้ในรูปที่ ๒
  2. ขั้นที่สองและเป็นขั้นสุดท้ายปลายทางซ้ายและขวาของแกนที่ 2 สลับที่กันและของเล่นจะอยู่ที่ปลายด้านขวาของแกนที่ 2 ดังแสดงไว้ในรูปที่ ๓


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

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

ข้อมูลนำเข้า
บรรทัดแรก เป็นตัวเลขจำนวนเต็ม n มีค่าอยู่ระหว่าง (1 ≤ n ≤ 100 000) ซึ่งแสดงถึงจำนวนแกนใน โมบายแกนจะถูกกำหนดตัวเลขตั้งแต่ 1,2,…,n
บรรทัดต่อมาอีก n บรรทัด เป็นการบรรยายถึงการเชื่อมต่อกันของแกนแต่ละอัน เช่น บรรทัดที่ i ของกลุ่มบรรทัดในส่วนนี้แสดงถึงแกนหมายเลข i แต่ละบรรทัดจะมีตัวเลขจำนวนเต็ม 2 ตัว l และ r แยกกันด้วยช่องว่างหนึ่งช่อง ซึ่งจะเป็นตัวที่บอกว่ามีอะไรแขวนอยู่ทางด้านซ้ายและด้านขวาของแกนนั้น ถ้ามีของเล่นแขวนอยู่ภายใต้แกนนี้ค่าของ l และ r จะมีค่าเป็น -1 ถ้าไม่เช่นนั้นค่าตัวเลข l และ r จะหมายถึงแกนที่แขวนอยู่ภายใต้แกนนั้น

ถ้ามีแกนใดที่อยู่ใต้แกน i, แกนเหล่านั้นจะต้องมีหมายเลขแกนมากกว่า i เสมอ และแกนหมายเลข 1 เป็นแกนเดียวที่อยู่บนสุดของโมบาย

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

ที่มา: Asia-Pacific Informatics Olympiad 2007

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

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

กำลังออนไลน์: 19 ผู้เยี่ยมชมและ 4 สมาชิก (0 บอท)