Problem
एन शहर में, अस्पष्ट परिस्थितियों में, कारखानों में से एक का क्षेत्र एक विषम क्षेत्र में बदल गया। क्षेत्र के सभी प्रवेश द्वार अवरुद्ध थे, और इसे ही औद्योगिक क्षेत्र कहा जाता था। औद्योगिक क्षेत्र में
N भवन हैं, उनमें से कुछ सड़कों से जुड़े हुए हैं। किसी भी सड़क पर दोनों दिशाओं में जाया जा सकता है।
नौसिखिए शिकारी को औद्योगिक क्षेत्र में गोदाम में जाने का काम दिया गया था। उन्होंने इलेक्ट्रॉनिक संग्रह में औद्योगिक क्षेत्र के क्षेत्र के कई नक्शे पाए। चूंकि नक्शे अलग-अलग लोगों द्वारा संकलित किए गए थे, उनमें से प्रत्येक में केवल औद्योगिक क्षेत्र की कुछ सड़कों के बारे में जानकारी होती है। एक ही सड़क कई मानचित्रों पर दिखाई दे सकती है।
रास्ते में, स्टाकर आर्काइव से मोबाइल फोन पर एक कार्ड डाउनलोड कर सकता है। जब आप एक नया मानचित्र डाउनलोड करते हैं, तो पिछला वाला फ़ोन की मेमोरी में संग्रहीत नहीं होता है। शिकारी केवल वर्तमान में लोड किए गए मानचित्र पर चिह्नित सड़कों पर ही चल सकता है। प्रत्येक मानचित्र डाउनलोड की लागत 1 रूबल है। लागत को कम करने के लिए, स्टाकर को नक्शे को जितनी बार संभव हो डाउनलोड करने के लिए ऐसा मार्ग चुनने की आवश्यकता होती है। स्टाकर एक ही नक्शे को कई बार डाउनलोड कर सकता है, और आपको प्रत्येक डाउनलोड के लिए भुगतान करना होगा। प्रारंभ में, मोबाइल फोन की मेमोरी में कोई कार्ड नहीं होता है।
एक ऐसा प्रोग्राम लिखना आवश्यक है जो औद्योगिक क्षेत्र के प्रवेश द्वार से गोदाम तक पहुंचने के लिए आवश्यक न्यूनतम खर्चों की गणना करता हो।
इनपुट:
- इनपुट की पहली लाइन में दो नेचुरल नंबर
N और
K (
\(2 <= N <= 2000) होते हैं \ );
\(1 <= K <= 2000\)) — औद्योगिक क्षेत्र की इमारतों की संख्या और मानचित्रों की संख्या, क्रमशः। औद्योगिक क्षेत्र का प्रवेश <कोड>1 वाले भवन में स्थित है, और गोदाम - mdash; बिल्डिंग नंबर <कोड>एन में।
- निम्नलिखित पंक्तियों में उपलब्ध कार्डों के बारे में जानकारी है।
iवें कार्ड के विवरण की पहली पंक्ति में
ri —
i-th मैप पर चिह्नित सड़कों की संख्या;
- फिर
ri दो प्राकृतिक संख्याओं
a और
b (
\(1 <= a\),
\(b <= N\);
\(a ? b\)), जिसका मतलब है कि
i-th मैप पर बिल्डिंग
a और
b< को जोड़ने वाली एक सड़क है / कोड>। सभी मानचित्रों पर चिह्नित सड़कों की कुल संख्या 300,000 से अधिक नहीं है (\(r_1 + r_2 + … + r_K <= 300,000\))।
आउटपुट: एक नंबर प्रिंट करें — शिकारी के खर्च की न्यूनतम राशि। यदि वेयरहाउस तक जाना असंभव है, तो –1 नंबर प्रिंट करें।
उदाहरण
<टेबल क्लास = "टेबल-बॉर्डर्ड टेबल-लिस्ट-टेस्ट टेबल-एसएम टेबल-स्ट्राइप्ड">
<सिर>
<वें>#
<वें>इनपुट
<वें>आउटपुट
<शरीर>
| 1 |
12 4
4
16
24
79
10 12
3
14
7 11
36
3
25
4 11
8 9
5
3 10
10 7
7 2
12 3
5 12 |
3 |