1133 : รถไฟใต้ดิน (subway)
Problem type : Batch
Time limit : 4.0 second(s)
Memory limit : 64 megabyte(s)
Problem type : Batch
Time limit : 4.0 second(s)
Memory limit : 64 megabyte(s)
พ.ศ. 2570 รัฐบาลได้ดำเนินโครงการก่อสร้างรถไฟใต้ดินซึ่งเป็นโครงการเมกะโปรเจกต์จนเสร็จสิ้น ทำให้กรุงเทพฯ กลายเป็นเมืองที่มีเครือข่ายรถไฟใต้ดินที่ใหญ่ที่สุดแห่งหนึ่งของโลก ประกอบด้วยเส้นทางรถไฟใต้ดินหลายร้อยสาย และสถานีอีกนับล้านสถานี
คุณต้องการเดินทางโดยรถไฟใต้ดินจากสถานีหนึ่งไปยังอีกสถานีหนึ่ง โดยในระหว่างทาง สามารถทำการเปลี่ยนสายรถไฟได้โดยการไปลงที่บางสถานีแล้วขึ้นรถไฟใต้ดินสายอื่นที่ผ่านสถานีนั้นต่อ แต่การเปลี่ยนสายรถไฟแต่ละครั้งก็ทำให้เสียเวลาเป็นอย่างมาก คุณจึงต้องการเดินทางโดยเปลี่ยนสายรถไฟให้น้อยครั้งที่สุดเท่าที่จะทำได้
งานของคุณ
จงเขียนโปรแกรมเพื่อตอบคำถามทั้งหมด Q คำถามว่า การเดินทางจากสถานี Ai ไปยังสถานี Bi จะต้องทำการเปลี่ยนสายรถไฟอย่างน้อยกี่ครั้ง
ข้อมูลนำเข้า
คุณต้องการเดินทางโดยรถไฟใต้ดินจากสถานีหนึ่งไปยังอีกสถานีหนึ่ง โดยในระหว่างทาง สามารถทำการเปลี่ยนสายรถไฟได้โดยการไปลงที่บางสถานีแล้วขึ้นรถไฟใต้ดินสายอื่นที่ผ่านสถานีนั้นต่อ แต่การเปลี่ยนสายรถไฟแต่ละครั้งก็ทำให้เสียเวลาเป็นอย่างมาก คุณจึงต้องการเดินทางโดยเปลี่ยนสายรถไฟให้น้อยครั้งที่สุดเท่าที่จะทำได้
งานของคุณ
จงเขียนโปรแกรมเพื่อตอบคำถามทั้งหมด 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
อีก 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
โจทย์โดย: สุธี เรืองวิเศษ
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 |
ความช่วยเหลือ: ไม่มีคำใบ้สำหรับปัญหานี้
กำลังออนไลน์: 21 ผู้เยี่ยมชมและ 0 สมาชิก (0 บอท)