একটি স্কুলে n জন শিক্ষার্থী আছে। তাদের মাঝে কেউ কেউ একে অপরের ফ্রেন্ড।
তুমি স্কুলটিকে পরিবেশ বান্ধব করতে চাও। এজন্য আপনাকে প্রতিটি শিক্ষার্থীকে আইসক্রিম দিতে হবে যাতে সে বৃক্ষ রোপন শুরু করে।
যখন একজন একটি বৃক্ষ রোপন করে, সে তার সকল বন্ধুদের এ সম্পর্কে বলে এবং তার বন্ধুরা সবাই একটি করে বৃক্ষ রোপন করতে শুরু করে (কোনো আইস্ক্রিম ছাড়াই) এবং এভাবে চলতে থাকে।
i-তম শিক্ষার্থী ট্রেন্ডটি শুরু করার জন্য xi আইসক্রিম চায়।
যখন n জন শিক্ষার্থী বৃক্ষরোপন শুরু করবে তখন তোমার কাজ শেষ হবে। সর্বনিম্ন কয়টি আইস্ক্রিম দিয়ে কাজটি শেষ করা সম্ভব?
প্রথম লাইনে দুইটি ইন্টিজার n এবং k থাকবে যারা যথাক্রমে শিক্ষার্থীর সংখ্যা এবং যে কয় জোড়া শিক্ষার্থী একজন আরেকজনের বন্ধু তা নির্দেশ করবে।
দ্বিতীয় লাইনে n সংখ্যক ইন্টিজার নাম্বার xi (0 <= xi <= 109) থাকবে।
এরপর k সংখ্যক লাইন থাকবে যার প্রত্যেকটায় এক জোড়া নাম্বার(a,b) থাকবে যেখানে a এবং b একে অপরের বন্ধু (1 <= a,b <= n) এবং a ও b সমান নয়।
Constrains:
For 10 points: 1 ≤ n ≤ 700, 0 ≤ k ≤ 300
For 40 points: 1 ≤ n ≤ 105, 0 ≤ k ≤ 1200
For 100 points: 1 ≤ n ≤ 105, 0 ≤ k ≤ 105
সর্বনিম্ন কতটি আইসক্রিম লাগবে সেটি প্রিন্ট করতে হবে।
Input | Output |
---|---|
10 5 1 6 2 7 3 8 4 9 5 10 1 2 3 4 5 6 7 8 9 10 | 15 |