একটি আনওয়েইটেড এবং আনডিরেক্টেড গ্রাফ লুকানো আছে। তোমাকে একটি পূর্ণসংখ্যার পরিসর দেওয়া আছে থেকে পর্যন্ত। গ্রাফটিতে মোট সংখ্যক নোড আছে এবং তাদের চিহ্নিত করা যাবে নাম্বার থেকে পর্যন্ত। দুটি নোড এবং এর মাঝে সরাসরি সংযোগ রয়েছে যদি এর মান 1 এর চেয়ে বড় হয়।
তোমাকে ওই গ্রাফের কানেক্টেড কম্পোনেন্ট ের সংখ্যা খুজে বের করতে হবে। এবং প্রতিটি কানেক্টেড কম্পোনেন্ট এ মোট নোড এর সংখ্যা খুজে বের করতে হবে।
আনওয়েইটেড এবং আনডিরেক্টেড গ্রাফ এর পরিচিতি এখানে পাওয়া যাবে।
কানেক্টেড কম্পোনেন্ট এর পরিচিতি এখানে পাওয়া যাবে।
ইনপুট এর প্রথম লাইনে একটি পূর্ণসংখ্যা থাকবে। যা মোট টেস্টকেস এর সংখ্যা নির্দেশ করে।
প্রতিটি টেস্টকেস এ দুটি পূর্ণসংখ্যা L এবং R থাকবে।
40 পয়েন্ট অর্জন এর জন্যঃ
60 পয়েন্ট অর্জন এর জন্যঃ
প্রতিটি টেস্টকেস এর প্রথম লাইনে একটি পূর্ণসংখ্যা X থাকবে, যা গ্রাফে মোট কানেক্টেড কম্পোনেন্ট এর সংখ্যা নির্দেশ করে।
তারপর সর্বমোট লাইনের প্রতি লাইনে একটি করে কম্পোনেন্ট এর সাইজ থাকবে ছোট থেকে বড় আকারে সাজানো।
Input | Output |
---|---|
2 1 9 2 7 | 4 1 1 1 6 3 1 1 4 |
Hidden graph for the first test case: The greatest common divisor for the following pairs is greater than 1: , , , , , , , , . Each pair of nodes above share a common edge between them. So, there are 3 components consists of 1 node and another component with 6 nodes. |
প্রথম টেস্ট কেস এর জন্য গুপ্ত গ্রাফ নিম্নরূপঃ
নিচের সংখ্যা যুগলদ্বয়ের গরিষ্ঠ সাধারন গুণনীয়ক 1 এর চেয়ে বেশীঃ
(2,4), (2,6), (2,8), (4,6), (4,8), (6,8), (3,6), (3,9), (6,9).
এই সংখ্যা যুগলরা নিজেদের মাঝে একটি করে সাধারন এজ (Edge) দিয়ে সরাসরি সংযুক্ত। এখানে মোট 3 টি কম্পোনেন্ট রয়েছে 1 করে নোড নিয়ে, আরেকটি কম্পোনেন্ট রয়েছে 6 টি নোড সমৃদ্ধ।