Masala #0736
Graf ichidan to'plam
Sizga Grafning tugunlar soni \(N\) berilgan. Grafdagi tugunlar 1 dan N gacha nomerlangan. Grafda barcha \(u \% v == 0 (2 \le u, v \le n)\) shartni qanoatlantiradigan tugunlar orasida to’g’ridan to’g’ri yo’l mavjud. Siz quyidagi shartlarni qanoatlantiradigan to’plamni hosil qiling:
- To’plam elementlar soni imkon qadar kam bo’lsin
- Grafning barcha tuguni uchun quyidagi shartlardan biri bajarilsin:
- Tugun to’plam ichida mavjud bo’lsin
- Tugun bilan to’g’ridan to’g’ri yo’l mavjud bo’lgan boshqa bir tugun to’plam ichida mavjud bo’lsin
Kiruvchi ma'lumotlar:
Kirish faylining dastlabki satrida bitta butun son, \(T (1 \le T \le 10^5)\) testlar soni kiritiladi.
Keyingi \(T\) ta qatorda bittadan butun son, \(N (1 \le N \le 10^6)\) graf tugunlar soni kiritiladi.
Chiquvchi ma'lumotlar:
Chiqish faylida har bir test uchun alohida qatorda hosil qilingan to’plamning minimal uzunligi nechchi bo’lishini chop eting!
Misollar
| # | input.txt | output.txt |
|---|---|---|
| 1 |
1 6 |
4 |
Izoh:
1-testda:
Grafda 2-4, 2-6, 3-6 yo’llar mavjud
To’plamni (1,4,5,6) qiymatlardan hosil qilsa bo’ladi.
Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring,
agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin
Telegram kanalimizga obuna bo'ling