Masala #0736

Xotira 16 MB Vaqt 1000 ms Qiyinchiligi 30 %
2.8 (Baholar 4)
14

  

Graf ichidan to'plam

Sizga Grafning tugunlar soni NN berilgan. Grafdagi tugunlar 1 dan N gacha nomerlangan. Grafda barcha u%v==0(2u,vn)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(1T105)T (1 \le T \le 10^5) testlar soni kiritiladi.

Keyingi TT ta qatorda bittadan butun son, N(1N106)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