सही ऐरे (Perfect Array) का निर्माण
आप एक कंप्यूटर वैज्ञानिक दोस्त की एक शोध परियोजना में मदद कर रहे हैं। इस परियोजना के लिए एक ऐसा ऐरे (array) खोजने की ज़रूरत है, जो कुछ दिए गए प्रतिबंधों (constraints) को पूरा करे। विशेष रूप से, आपको लंबाई
n वाले ऐरे a के लिए p जोड़ी इंडेक्स i और j दिए गए हैं। प्रत्येक जोड़ी (i, j) इस शर्त को व्यक्त करती है कि को से छोटा होना चाहिए। आपका कार्य यह ढूँढना है कि क्या ऐसा ऐरे a बनाया जा सकता है जो इन सभी शर्तों को पूरा करे।इस ऐरे
a के सभी पूर्णांक 1 से लेकर (सहित) के बीच होने चाहिए।इनपुट
इनपुट की पहली पंक्ति में दो पूर्णांक
n (2 ≤ n ≤ ) और p (1 ≤ p ≤ ) होते हैं, जहाँ n ऐरे a की लंबाई तथा p जोड़ी की संख्या को दर्शाता है। इसके बाद की प्रत्येक p पंक्ति में दो रिक्त स्थानों से अलग किए गए पूर्णांक i और j (1 ≤ i < j ≤ n) दिए जाते हैं, जो उन इंडेक्स की जोड़ी है जिन्हें की शर्त पूरी करनी होगी।आउटपुट
यदि ऐसा ऐरे
a संभव है जो सभी शर्तों को पूरा करे, तो एक ही पंक्ति में n स्थान-से-पृथक पूर्णांक प्रिंट करें, जो ऐरे a का प्रतिनिधित्व करते हों। इन पूर्णांकों की मान सीमा 1 से लेकर (सहित) होनी चाहिए। यदि एक से अधिक समाधान संभव हों, तो उनमें से कोई भी प्रिंट किया जा सकता है।यदि ऐसा ऐरे बनाना असंभव हो, तो प्रोग्राम को
Impossible प्रिंट करना चाहिए।उदाहरण
इनपुट | आउटपुट |
4 2
1 2
4 1 | 2 3 4 1 |
5 5
1 2
2 3
3 4
5 4
2 5 | 2 4 6 8 5 |
3 3
1 2
2 3
3 1 | Impossible |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB