ไวรัสอิไต (acm15_itai)


Time limit:
1000 ms
Memory limit:
64 MB

“Insane Transferable Abnormal Illness” หรือ โรค ITAI เป็นโรคที่เกิดจากไวรัสชนิดใหม่ที่อุบัติขึ้นในแนวชายฝั่งทางตอนใต้ของเมืองๆหนึ่ง โดยผู้ที่ติดเชื้อจะมีอาการกรีดร้องคำว่า “Itai, itai!” อย่างต่อเนื่องและไม่สามารถควบคุมไม่ได้

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

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

จงเขียนโปรแกรมเพื่อหาจำนวนเมืองทั้งหมดที่มีไวรัสอยู่หลังจากเกิดการแพร่กระจายจนไวรัสไม่สามารถกระจายได้อีกแล้ว

Input

บรรทัดแรกรับจำนวนคำถาม T (1 ⩽ T ⩽ 10)

คำถามที่ i (1 ⩽ i ⩽ T)

บรรทัดแรกของคำถามที่ i รับจำนวนเต็มสามจำนวนคือ N แทนจำนวนเมือง M แทนเส้นทางในประเทศ และ K แทนจำนวนเมืองที่มีการอุบัติของไวรัส (1 ⩽ N ⩽ 1000; 1 ⩽ M ⩽ 2N; 0 ⩽ K ⩽ N)

ต่อมาอีก M บรรทัดของคำถามที่ i รับจำนวนเต็ม A และ B แทนหมายเลขของเมืองที่มีเส้นทางติดต่อกัน

บรรทัดต่อมารับจำนวนเต็มทั้งหมด K จำนวน แต่ละจำนวนแทนหมายเลขของเมืองที่มีการอุบัติของไวรัส

Output

มีทั้งหมด T บรรทัด โดยบรรทัดที่ i ให้แสดงจำนวนเมืองทั้งหมดที่มีไวรัสอยู่หลังจากเกิดการแพร่กระจายจนไวรัสไม่สามารถกระจายได้อีกแล้วในคำถามที่ i

Editor:

Source: ACM ICPC 2015 Thailand Local Central Group B

Select description language

Thai (raw)
English (raw)

If you don't find what you want

Translate it!

Edit this description

Edit

Tag

None