ড্রাগন কুইন সদ্যই সেভেন কিংডমস জয় করেছেন। প্রাথমিকভাবে সেখানে N সংখ্যক শহর রয়েছে সেভেন কিংডমস এ এবং তাদের 1 থেকে N পর্যন্ত
সংখ্যা দিয়ে নামকরম করা হয়েছে।
সেই শহরগুলো M সংখ্যক ডিরেক্টেড রাস্তা দিয়ে সংযুক্ত। এমন হতেই পারেন যে এক শহর থেকে আরেক শহরে যাওয়ার কোন রাস্তা নেই।
এই মহান(?) এই মহান বিজয়ের পর ড্রাগন কুইন ঘোষণা দিলেন যে, যখনই কোন ব্যক্তি কোন রাস্তা পার করবেন তখন তিনি C স্বর্ণমুদ্রা পাবেন। এই C এর মাণ রাস্তা .ভেদে ভিন্ন হতে পারে।
একটু চিন্তা করে দেখুন কি হবে যদি কিছু শহর মিলে সাইক্লিক পাথ তৈরি করে! যদি কোন ব্যক্তি এখন X শহরে থাকেন এবং এই শহরটি একটি সাইকেলের অংশ তাহলে সেই ব্যক্তি কিন্তু অসীম সংখ্যক স্বর্ণমুদ্রা আহরণ করতে পারবেন। যা **আইরন ব্যাংক ** ও দিতে পারবে না।
রানীর হাত বলে পরিচিত টাইরিওন ল্যানিস্টার একটি বুদ্ধিমান ধারণা দিলেন। তারা কিছু শহরের সাবসেট নির্বাচন করবেন। এবং সেই শহর/শহরগুলোকে শুধুমাত্র একটি শহরে পরিণত করবেন। এবং তাদের নিজেদের মধ্যে থাকা রাস্তাগুলো ধ্বংস করে দেওয়া হবে।
ধরি দুইটি নতুন বানানো শহর হচ্ছে A আর ** B**। যে শহর/ শহরগুচ্ছ নিয়ে **A** বানানো হয়েছে, তাদের মধ্যে কোন শহর থেকে যদি শহর **B** তে যাওয়ার কোন রাস্তা থেকে থাকে তাহলে নতুন মানচিত্রে **A** থেকে **B** তে যাওয়ার একটি রাস্তা থাকবে। এবং **C** এর মাণ অপরিবর্তিত থাকবে।
তারা সেভেন কিংডমস এর মানচিত্র এমন ভাবে পরিবর্তন করবে যেন নতুন মানচিত্রে শহরের সংখ্যা সর্বোচ্চ হয় এবং কোন সাইক্লিক রাস্তা যেন না থাকে।
আমরা সবাই জানি জন স্নো একেরপর এক যুদ্ধ করতে করতে গরীব হয়ে গেছেন। এখন সে পরিকল্পনা করেছেন সেই রাস্তাগুলো দিয়ে ভ্রমণ শুরু করার এবং যতো বেশী সম্ভব অর্থ সংগ্রহ করার।
আপনি তার খুবই ভালো বন্ধু।
সে আপনাকে Q সংখ্যক ইন্ডিপেনডেন্ট কুয়েরি জিজ্ঞেস করবেন। প্রতি কুয়েরিতে সে আপনাকে শহর X এর কথা বলবে এবং সেই নাম্বারটি হবে শহর এর মানচিত্র বদলের আগে শহরটি যে নামে ডাকা হতো সেই নাম্বার। এবং আপনাকে বলতে হবে সে যদি নতুন মানচিত্রে ঐ শহর থেকে যাত্রা শুরু করে তাহলে সে সর্বোচ্চ কতো স্বর্ণমুদ্রা সংগ্রহ করতে পারবেন।
ইনপুটের প্রথম লাইনে থাকবে তিনটি ইন্টিজার N , M আর Q (1≤N,M≤10^5, 0≤Q≤10^5) যথাক্রমে শহরের সংখ্যা, মোট রাস্তার সংখ্যা আর কুয়েরির সংখ্যা।
তারপরের M লাইনের প্রতিটিতে থাকবে তিনটি ইন্টিজার U, V আর C (1≤U,V≤N, 1≤C≤10^5) মানে শহর U থেকে শহর V তে একটি রাস্তা রয়েছে এবং একজন সেই রাস্তা পার হওয়ার সময় C স্বর্ণমুদ্রা পাবেন।
পরের Q লাইনের প্রতিটিতে থাকবে একটি ইন্টিজার X (1<=X<=N )
40 পয়েন্টের জন্য: 1 <= N, M, Q <= 10000
100 পয়েন্টের জন্য: 1 <= N, M, Q <= 100000
প্রতি কুয়েরির জন্য আপনাকে আলাদা লাইনে প্রিন্ট করতে হবে যদি জন স্নো শহর X.থেকে যাত্রা শুরু করে তাহলে সে কতো স্বর্ণমুদ্রা সংগ্রহ করতে সমর্থ হবেন।
Input | Output |
---|---|
6 6 6 1 2 10 2 3 12 3 2 13 3 4 15 3 5 2 5 6 3 1 2 3 4 5 6 | 25 15 15 0 3 0 |