ग्राफ को पूर्ण बनाएं
एक निर्देशरहित ग्राफ दिया गया है जिसमें v शीर्ष (vertices) और e धाराएं (edges) मौजूद हैं। आपका काम उन सभी धाराओं को खोजने का है, जिन्हें जोड़कर यह ग्राफ पूर्ण (complete) बन सके।
इनपुट
इनपुट की पहली पंक्ति में दो पूर्णांक v (1 ≤ v ≤ 500) और e (1 ≤ e ≤ ) दिए होते हैं।
अगली e पंक्तियों में प्रत्येक पंक्ति में v1, v2 (1 ≤ v1, v2 ≤ v) की एक जोड़ी होती है, जो v1 और v2 के बीच की धारा दर्शाती है।
आउटपुट
प्रोग्राम को उन सभी नई धाराओं को छापना होगा जो ग्राफ में जोड़नी जरूरी हैं, ताकि यह पूर्ण हो जाए। इन धाराओं को लексिकोग्राफिकल क्रम में (सबसे छोटे शीर्ष आईडी से सबसे बड़े की ओर) छापा जाए। प्रत्येक धारा एक अलग पंक्ति पर हो, और दोनों शीर्षों को खाली जगह (space) से अलग किया जाए।
उदाहरण
इनपुट | आउटपुट |
4 3
1 2
2 3
3 1 | 1 4
2 4
3 4 |
व्याख्या
- प्रारंभ में, ग्राफ में मौजूद किसी भी शीर्ष से 4 जुड़ा नहीं था। इसलिए, उसे बाक़ी सभी शीर्षों से जोड़ना आवश्यक हो गया।
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB