মডিউল ১৫_৫ঃ D. Roads not only in Berland

বার্ল্যান্ড সরকার প্রতিবেশী দেশগুলির সাথে সম্পর্ক উন্নত করার সিদ্ধান্ত নিয়েছে। প্রথমত, নতুন রাস্তা তৈরি করার সিদ্ধান্ত নেওয়া হয়েছিল যাতে বার্ল্যান্ডের প্রতিটি শহর এবং প্রতিবেশী দেশগুলি থেকে অন্য সকলের কাছে পৌঁছানো সম্ভব হয়। বার্ল্যান্ড এবং প্রতিবেশী দেশগুলিতে মোট n টি শহর রয়েছে এবং ঠিক n - 1 টি দ্বিমুখী রাস্তা রয়েছে ৷ সাম্প্রতিক আর্থিক সংকটের কারণে, বার্ল্যান্ড সরকার অর্থের জন্য জোরালোভাবে চাপ দিচ্ছে, তাই একটি নতুন রাস্তা তৈরি করতে আরেকটি বিদ্যমান রাস্তাকে বন্ধ করতে হবে। প্রতিদিন একটি বিদ্যমান রাস্তা বন্ধ করে অবিলম্বে একটি নতুন নির্মাণ করা সম্ভব। আপনার কাজ হল রাস্তাগুলি পুনর্নির্মাণের জন্য কত দিনের প্রয়োজন হবে তা নির্ধারণ করা যাতে প্রতিটি শহর থেকে অন্য সকলের কাছে পৌঁছানো সম্ভব হয়।

ইনপুট

7 -> number of cities 1 2 2 3 3 1 4 5 5 6 6 7

Graph টি এইরকম হবে

cycle পেলেই সেই edge গুলোর road গুলোকে বাদ দিব।

উপরের চিত্রে 1 , 3 edge কে বাদ দেয়া হয়েছে। এখন 1 অথবা 3 কে দিয়ে সব নোডের সাথে চেক করে দেখবো তাদের leader অমিল পাওয়া যায় কিনা। নিচের চিত্রে 1 হচ্ছে leader (1, 2, 3) graph টির, 1 leader 1 নিজেই আর অন্য দিকে 2 এবং 3 নোডের leader ও 1 , তাই 1 সাথে 2 অথবা 3 সাথে নতুন connection করতে পারবে নাহ। এরপর 1 এর leader এর সাথে 4 নোডের leader অমিল , এর ফলে 1 এবং 4 এর মাঝে নতুন একটি connection করে road create করা যাবে।

এইভাবে উপরে গ্রাফটির আউটপুট হবে প্রব্লেমটির জন্য। 1 1 3 1 4