Masala #0736
Graf ichidan to'plam
Sizga Grafning tugunlar soni berilgan. Grafdagi tugunlar 1 dan N gacha nomerlangan. Grafda barcha 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
Kirish faylining dastlabki satrida bitta butun son, testlar soni kiritiladi.
Keyingi ta qatorda bittadan butun son, graf tugunlar soni kiritiladi.
Chiqish faylida har bir test uchun alohida qatorda hosil qilingan to’plamning minimal uzunligi nechchi bo’lishini chop eting!
# | input.txt | output.txt |
---|---|---|
1 |
1 6 |
4 |
1-testda:
Grafda 2-4, 2-6, 3-6 yo’llar mavjud
To’plamni (1,4,5,6) qiymatlardan hosil qilsa bo’ladi.