1133 : รถไฟใต้ดิน (subway)
Problem type : Batch
Time limit : 4.0 second(s)
Memory limit : 64 megabyte(s)
พ.ศ. 2570 รัฐบาลได้ดำเนินโครงการก่อสร้างรถไฟใต้ดินซึ่งเป็นโครงการเมกะโปรเจกต์จนเสร็จสิ้น ทำให้กรุงเทพฯ กลายเป็นเมืองที่มีเครือข่ายรถไฟใต้ดินที่ใหญ่ที่สุดแห่งหนึ่งของโลก ประกอบด้วยเส้นทางรถไฟใต้ดินหลายร้อยสาย และสถานีอีกนับล้านสถานี

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

งานของคุณ
จงเขียนโปรแกรมเพื่อตอบคำถามทั้งหมด Q คำถามว่า การเดินทางจากสถานี Ai ไปยังสถานี Bi จะต้องทำการเปลี่ยนสายรถไฟอย่างน้อยกี่ครั้ง

ข้อมูลนำเข้า
บรรทัดแรกระบุจำนวนเต็ม N และ M (2 ≤ N ≤ 1,000,000; 1 ≤ M ≤ 500) แทนจำนวนสถานีทั้งหมดและจำนวนสายของรถไฟใต้ดิน

อีก M บรรทัดต่อมา ในบรรทัดที่ i+1 (1 ≤ i ≤ M) ระบุจำนวนเต็มตัวแรกคือ Si (2 ≤ Si ≤ 2,000) แทนจำนวนสถานีที่รถไฟใต้ดินสายที่ i ผ่าน และจำนวนเต็มอีก Si จำนวนถัดมา ระบุหมายเลขของสถานีที่รถไฟใต้ดินสายดังกล่าวผ่าน เรียงตามลำดับจากปลายทางข้างหนึ่งไปจนถึงปลายทางอีกข้างหนึ่ง

บรรทัดถัดมา ระบุจำนวนเต็ม Q (2 ≤ Q ≤ 1,000,000) แทนจำนวนคำถามทั้งหมด

อีก Q บรรทัดถัดมา ในบรรทัดที่ i+M+2 (1 ≤ i ≤ Q) ระบุจำนวนเต็ม Ai และ Bi (1 ≤ Ai,Bi ≤ N) แสดงถึงคำถามที่ i

สถานีแต่ละสถานีจะมีรถไฟใต้ดินผ่านไม่เกิน 20 สาย โดยที่บางสถานีอาจไม่มีรถไฟใต้ดินผ่านเลยแม้แต่สายเดียวก็ได้ นอกจากนี้เส้นทางของรถไฟใต้ดินแต่ละสายอาจผ่านบางสถานีมากกว่าหนึ่งครั้งก็ได้

ข้อมูลส่งออก
มีทั้งหมด Q บรรทัด ในบรรทัดที่ i (1 ≤ i ≤ Q) ให้พิมพ์จำนวนครั้งของการเปลี่ยนสายรถไฟที่น้อยที่สุดที่ต้องใช้ในการเดินทางจากสถานี Ai ไปยังสถานี Bi แต่ถ้าไม่สามารถเดินทางโดยรถไฟใต้ดินจากสถานี Ai ไปยังสถานี Bi ได้ ให้พิมพ์คำว่า impossible

การให้คะแนน
50% ของข้อมูลทดสอบ จะมี N ≤ 1,000; M ≤ 100; Q ≤ 1,000 และมี Si ≤ 20 สำหรับทุกจำนวนเต็ม i (1 ≤ i ≤ M)

ที่มา
การแข่งขัน IOI Thailand League เดือนกันยายน 2553
โจทย์โดย: สุธี เรืองวิเศษ

ตัวอย่างข้อมูลนำเข้า ตัวอย่างข้อมูลส่งออก
6 2
3 1 2 3
3 2 4 5
3
1 3
1 4
2 6
0
1
impossible
15 5
6 1 2 3 4 2 5
2 6 7
4 1 6 8 9
4 10 11 12 13
3 14 11 15
6
9 2
10 13
10 5
3 7
6 14
15 12
1
0
impossible
2
impossible
1

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

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