Limits 1s, 512 MB

একটি স্কুলে n জন শিক্ষার্থী আছে। তাদের মাঝে কেউ কেউ একে অপরের ফ্রেন্ড।
তুমি স্কুলটিকে পরিবেশ বান্ধব করতে চাও। এজন্য আপনাকে প্রতিটি শিক্ষার্থীকে আইসক্রিম দিতে হবে যাতে সে বৃক্ষ রোপন শুরু করে।
যখন একজন একটি বৃক্ষ রোপন করে, সে তার সকল বন্ধুদের এ সম্পর্কে বলে এবং তার বন্ধুরা সবাই একটি করে বৃক্ষ রোপন করতে শুরু করে (কোনো আইস্ক্রিম ছাড়াই) এবং এভাবে চলতে থাকে।

i-তম শিক্ষার্থী ট্রেন্ডটি শুরু করার জন্য xi আইসক্রিম চায়।
যখন n জন শিক্ষার্থী বৃক্ষরোপন শুরু করবে তখন তোমার কাজ শেষ হবে। সর্বনিম্ন কয়টি আইস্ক্রিম দিয়ে কাজটি শেষ করা সম্ভব?

Input

প্রথম লাইনে দুইটি ইন্টিজার 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

Output

সর্বনিম্ন কতটি আইসক্রিম লাগবে সেটি প্রিন্ট করতে হবে।

Sample

InputOutput
10 5
1 6 2 7 3 8 4 9 5 10
1 2
3 4
5 6
7 8
9 10
15

Submit

Login to submit.

Statistics

66% Solution Ratio
nahidhasan98Earliest, Oct '19
nnnnnnFastest, 0.0s
subhashis_cseLightest, 524 kB
Jabir.837748Shortest, 544B
Toph uses cookies. By continuing you agree to our Cookie Policy.