Problem
शीर्ष-गुप्त संगठनों में से एक, जिसका नाम हमें प्रकट करने की अनुमति नहीं है, समान लंबाई की सुरंगों से जुड़े <कोड>एन भूमिगत बंकरों का एक नेटवर्क है, जिसके माध्यम से कोई भी बंकर से किसी अन्य बंकर तक पहुंच सकता है ( जरूरी नहीं कि सीधे)। बाहरी दुनिया के साथ संचार विशेष गुप्त निकास के माध्यम से किया जाता है, जो कुछ बंकरों में स्थित हैं।
किसी आपात स्थिति के मामले में संगठन को एक कर्मचारी निकासी योजना तैयार करने की आवश्यकता थी। ऐसा करने के लिए, प्रत्येक बंकर के लिए, आपको यह पता लगाना होगा कि निकटतम निकास तक पहुंचने में कितना समय लगेगा। आपको ऐसे कार्यों के विशेषज्ञ के रूप में, शीर्ष गुप्त संगठन के परिसर के दिए गए विवरण के अनुसार प्रत्येक बंकर के लिए आवश्यक समय की गणना करने का निर्देश दिया जाता है। आपकी सुविधा के लिए, बंकरों को
1 से
N तक क्रमांकित किया गया है।
इनपुट:
- पहली दो पंक्तियों में दो प्राकृत संख्याएँ हैं
N,
K (
\(1 <= N <= 100000\) ,
\(1 <= K <= N\)) — बंकरों की संख्या और बाहर निकलने की संख्या क्रमशः;
- तीसरी पंक्ति में,
K अलग-अलग नंबरों को
1 से
N तक स्पेस से अलग किया गया है, जो उन बंकरों की संख्या को दर्शाता है जहां निकास स्थित हैं;
- चौथी पंक्ति में संख्या
M (
\(1 <= M <= 100000\)) — सुरंगों की संख्या;
- निम्नलिखित <कोड>म पंक्तियां संख्याओं के जोड़े में प्रवेश करती हैं – सुरंग से जुड़े बंकरों की संख्या।
प्रत्येक सुरंग दोनों दिशाओं में जा सकती है। एक संगठन के पास एक बंकर से स्वयं तक जाने वाली सुरंगें नहीं होती हैं, लेकिन बंकरों की एक जोड़ी के बीच एक से अधिक सुरंग हो सकती हैं।
आउटपुट: N स्पेस से अलग किए गए नंबर प्रिंट करें — प्रत्येक बंकर के लिए, बाहर निकलने के लिए आवश्यक न्यूनतम समय। मान लें कि एक टनल से गुजरने में लगने वाला समय
1 है।
उदाहरण
<टेबल क्लास = "टेबल-बॉर्डर्ड टेबल-लिस्ट-टेस्ट टेबल-एसएम टेबल-स्ट्राइप्ड">
<सिर>
<वें>#
<वें>इनपुट
<वें>आउटपुट
<शरीर>
| 1 |
3
1
2
3
1 2
3 1
2 3
| 1 0 1 |
| 2 |
10
2
10 8
9
67
75
58
8 1
1 10
10 3
34
49
9 2
| 1 4 1 2 1 3 2 0 3 0 |