ट्री का डायामीटर (Diameter) खोजें
आपको एक ट्री दिया गया है जिसमें
v वर्टेक्स (vertices) हैं। आपका कार्य इस ट्री का डायामीटर ढूँढना है। ट्री का डायामीटर उन दो सबसे दूर वर्टेक्स के बीच के रास्ते की लंबाई होती है।इनपुट
इनपुट की पहली पंक्ति में एकमात्र पूर्णांक
v (1 ≤ v ≤ 100000) दिया गया है।इसके बाद की
v-1 पंक्तियों में प्रत्येक पंक्ति में दो पूर्णांक v1, v2 (1 ≤ v1, v2 ≤ v) दिए गए हैं, जो दर्शाते हैं कि v1 वर्टेक्स v2 वर्टेक्स से कनेक्टेड है और इसका उलटा भी सही है।आउटपुट
कार्यक्रम को दिए गए ट्री का डायामीटर प्रिंट करना चाहिए।
उदाहरण
इनपुट | आउटपुट |
3
1 2
1 3 | 2 |
5
1 2
1 3
3 4
3 5 | 3 |
संकेत 1
आप अलग-अलग सोर्स (sources) से कई बार DFS चला सकते हैं।
संकेत 2
आप नोड 1 से DFS शुरू करके सबसे दूर स्थित वर्टेक्स खोज सकते हैं (क्योंकि यह एक ट्री है, जिसमें साइकल नहीं होता, इसलिए हम इसे BFS के बिना भी कर सकते हैं)।
इसके बाद, जिस वर्टेक्स को सबसे दूर पाया गया, वहाँ से फिर से DFS शुरू करें और उससे भी सबसे दूर वर्टेक्स खोजें।
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB