Bicycle Slopes (साइकिल की चढ़ाई-उतराई)
Emil शहर
1 से शहर n तक साइकिल से यात्रा करना चाहता है, लेकिन इन शहरों को जोड़ने वाली सड़कों का ढलान उसके लिए चुनौती बन सकता है। हर सड़क या तो चढ़ाई वाली है या उतराई वाली। जब Emil चढ़ाई वाली सड़क से उतराई वाली सड़क पर (या इसके उलट) जाता है, तो आरामदायक सफ़र बनाए रखने के लिए उसे साइकिल का गियर बदलना पड़ता है। Emil जानना चाहता है कि शहर 1 से शहर n तक जाते समय उसे कम से कम कितनी बार गियर बदलने होंगे।इसलिए, आपको यह गणना करनी है कि Emil को शहर
1 से शहर n तक पहुंचने के लिए कम से कम कितनी बार गियर बदलना पड़ेगा।इनपुट
पहली पंक्ति में दो रिक्त स्थान से अलग किए गए पूर्णांक
n और m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000) होंगे, जो क्रमशः शहरों की संख्या और सड़कों की संख्या का प्रतिनिधित्व करते हैं।अगली
m पंक्तियों में से प्रत्येक में दो रिक्त स्थान से अलग किए गए पूर्णांक और दिए होते हैं (, ), जो शहर और के बीच बनी एक सड़क को दर्शाते हैं। से की ओर जाने वाली सड़क चढ़ाई है, जबकि से की ओर जाने वाली सड़क उतराई है।आउटपुट
शहर
1 से शहर n तक की यात्रा के दौरान Emil को गियर कितनी बार बदलने होंगे, इसकी न्यूनतम संख्या एक पूर्णांक के रूप में प्रिंट की जानी चाहिए।उदाहरण
इनपुट | आउटपुट |
5 5
1 2
2 3
5 3
4 2
4 5 | 1 |
3 3
1 2
2 3
3 1 | 0 |
Constraints
Time limit: 6 seconds
Memory limit: 512 MB
Output limit: 1 MB