Module: स्कैनलाइन विधि

अंत के पूर्णांक निर्देशांक वाले खंडों का एक निश्चित सेट \([L_i, R_i]\) एक रेखा पर दिया गया है। दिए गए सेट में से, सेगमेंट का एक ऐसा उपसमूह चुनें जो \([0, M]\), (M — प्राकृतिक संख्या) जिसमें सेगमेंट की सबसे छोटी संख्या है।

 

पहली पंक्ति में स्थिरांक M (\(1<=M<=5000\)) होता है। प्रत्येक अनुवर्ती पंक्ति में संख्याओं का एक जोड़ा होता है Li और Ri (\(|L_i|,|R_i| < 50000\)), जो खंडों के बाएँ और दाएँ सिरों के निर्देशांक निर्दिष्ट करता है। सूची शून्य की एक जोड़ी के साथ समाप्त होती है। सेगमेंट की कुल संख्या 100,000 से अधिक नहीं है।

 

आउटपुट फ़ाइल की पहली पंक्ति में \([0; M]\) सेगमेंट को कवर करने के लिए आवश्यक सेगमेंट की न्यूनतम संख्या प्रिंट करें। इसके बाद, सेगमेंट के बाएं सिरों के निर्देशांक द्वारा आरोही क्रम में क्रमबद्ध, कवरिंग सबसेट की एक सूची आउटपुट करें। खंडों की सूची इनपुट के समान प्रारूप में आउटपुट होती है। अनुगामी दो शून्य की आवश्यकता नहीं है। यदि खंड  \)< /span> संभव नहीं है, एक वाक्यांश "कोई समाधान नहीं” आउटपुट होना चाहिए।

 

उदाहरण

<टेबल क्लास = "टेबल-बॉर्डर्ड टेबल-लिस्ट-टेस्ट टेबल-एसएम टेबल-स्ट्राइप्ड"> <सिर> <वें># <वें>इनपुट <वें>आउटपुट <शरीर> 1 <टीडी> कोई समाधान नहीं 2 <टीडी> 1
0 1