Module: फैले हुए पेड़: क्रुस्कल का एल्गोरिथम

Problem

बेसी 1…N लेबल वाले N (2≤N≤10⁵) शीर्षों के नेटवर्क पर स्थित है और 1…2N लेबल वाले 2N पोर्टल्स पर स्थित है। प्रत्येक पोर्टल दो भिन्न शीर्षों u और v (u≠v) को जोड़ता है। पोर्टल्स का एक सेट कुछ शीर्षों को जोड़ सकता है।
प्रत्येक शीर्ष v चार अलग-अलग पोर्टलों के निकट है। वी के पोर्टल्स की सूची pv=[p_v,1,p_v,2,p_v,3,p< द्वारा दी गई है उप>वी,4]।

आपकी वर्तमान स्थिति को एक आदेशित जोड़ी (वर्तमान शीर्ष, वर्तमान पोर्टल) द्वारा दर्शाया जा सकता है; वह है, एक जोड़ी (v,p_v,i) जहां 1≤v≤N और 1≤i≤4। आप अपनी वर्तमान स्थिति को बदलने के लिए निम्न में से किसी एक ऑपरेशन का उपयोग कर सकते हैं:

वर्तमान पोर्टल के माध्यम से वर्तमान शीर्ष को बदलें।
वर्तमान पोर्टल स्विच करें। प्रत्येक शीर्ष पर, सूची में पहले दो पोर्टल जोड़े जाते हैं और सूची में अंतिम दो पोर्टल भी जोड़े जाते हैं। इसलिए यदि आपकी वर्तमान स्थिति (v,p_v,2) है, तो आप पोर्टल (v,p_v,1) और वापस उपयोग करने के लिए स्विच कर सकते हैं। इसी तरह, यदि आपकी वर्तमान स्थिति (v,p_v,3) है तो आप पोर्टल (v,p_v,4) और पीछे जा सकते हैं। किसी अन्य स्विचिंग की अनुमति नहीं है (उदाहरण के लिए आप पोर्टल pv,2 से पोर्टल पर स्विच नहीं कर सकते हैं) p_v,4)।
कुल 4N विभिन्न राज्य हैं। दुर्भाग्य से, ऐसा नहीं हो सकता है कि दिए गए कार्यों के अनुक्रम द्वारा किसी भी राज्य से किसी भी राज्य तक पहुंचा जा सकता है। इसलिए, cv (1≤c_v≤1000) चन्द्रमाओं की लागत के लिए, आप अपनी इच्छानुसार किसी भी क्रम में v के सन्निकट पोर्टल्स की सूची को पुनर्व्यवस्थित कर सकते हैं। उसके बाद, सूची में पहले दो पोर्टल्स को एक जोड़ी में जोड़ा जाता है, और अंतिम दो पोर्टल्स को दूसरी जोड़ी में जोड़ा जाता है।

उदाहरण के लिए, यदि आप v के पोर्टल्स को [p_v,3,p_v,1,p_v,2 क्रम में पुनर्व्यवस्थित करते हैं, p_v,4], इसका मतलब है। क्या होगा यदि आप शीर्ष वी पर हैं,

अगर आप p_v,1 पोर्टल में हैं, तो आप p_v,3 पोर्टल पर जा सकते हैं और वापस
अगर आप p_v,2 पोर्टल में हैं, तो आप p_v,4 पोर्टल पर जा सकते हैं और वापस
अब आप पोर्टल p_v,1 से p_v,2 या पोर्टल p_v,3 से पोर्टल p _{में स्विच नहीं कर सकते v,4} और इसके विपरीत।
नेटवर्क को संशोधित करने के लिए आवश्यक चंद्रमाओं की न्यूनतम संख्या की गणना करें ताकि प्रत्येक राज्य को प्रत्येक राज्य से पहुंच योग्य बनाया जा सके। यह गारंटी है कि परीक्षण डेटा इस तरह से बनाया गया है कि इस तरह से नेटवर्क को संशोधित करने का कम से कम एक तरीका है।

इनपुट: 
पहली लाइन में N है।
अगली N पंक्तियों में से प्रत्येक एक शीर्ष का वर्णन करती है। स्ट्रिंग v+1 में स्पेस से अलग किए गए 5 पूर्णांक हैं c_v,p_v,1,p_v,2,p_{v ,3},p_v,4।
यह गारंटी है कि प्रत्येक v के लिए सभी p_v,1,p_v,2,p_v,3,p_{v, 4} भिन्न हैं, और प्रत्येक पोर्टल बिल्कुल दो शीर्षों की सूची में प्रकट होता है।

आउटपुट: 
प्रत्येक राज्य को दूसरे राज्य से पहुंच योग्य बनाने के लिए एक पंक्ति में नेटवर्क को संशोधित करने के लिए आवश्यक चंद्रमाओं की न्यूनतम संख्या होती है।
 

उदाहरण

<टेबल क्लास = "टेबल-एसएम टेबल-बॉर्डर टेबल-स्ट्राइप्ड टेबल-लिस्ट-टेस्ट"> <सिर> <थ वर्ग = "अंक"> # <वें>इनपुट <वें>आउटपुट <थ>स्पष्टीकरण <शरीर> 1 5
10 1 4 8 9
11 1 2 5 6
12 9 10 2 3
3 4 3 6 7
15 10 8 7 5  13 शीर्ष 1 और 4 की सूचियों की अदला-बदली करना पर्याप्त है। इसके लिए c1+c4=13 मन की आवश्यकता है। क्रमपरिवर्तन हैं: p1=[1,9,4,8] और p4=[7,4,6,3]।