Masala #0673
Muhim tugunlar #5
ta tugun va ta qirradan iborat bog’langan yo’nalmagan graf berilgan. Ya’ni graf qirralari ikki tomonlamali hamda grafdagi ixtiyoriy tugundan boshqasiga qirralar orqali borish mumkin.
va tugunlar uchun muhim tugun deb shunaqangi tugunga aytiladiki , agar shu tugun grafdan olib tashlansa, grafda dan ga borishni imkoni bo’lmay qolsin.
Sizga ta so’rovlar orqali va tugunlar juftliklari beriladi, har bir so’rovdagi juftlik uchun muhim tugunlar sonini chiqaring.
Birinchi qatorda ikkita butun son tugunlar soni va qirralar soni kiritiladi . Keyingi ta qatorda graf qirralari va sonlar juftligi ko’rinishida beriladi .
Keyingi qatorda so’rovlar soni beriladi . Keyingi ta qatorda so’rovlarni ifodalovchi va sonlar juftligi beriladi .
1-subtask (11 ball): .
2-subtask (9 ball): Graf to’g’ri chiziq shaklida, ya’ni har bir tugunni bitta yoki ikkita qo’shnisi bo’lishi mumkin ( va ).
3-subtask (13 ball): hamda har bir bo’lgan -tugundan va tugunlarga qirra mavjud ( va ).
4-subtask (21 ball): va
5-subtask (46 ball):
Har bir so’rov uchun va tugunlar juftligiga nisbatan muhim bo’lgan tugunlar sonini chiqaring.
# | input.txt | output.txt |
---|---|---|
1 |
9 14 4 7 5 6 5 7 6 7 1 8 1 2 1 3 3 4 3 5 4 5 1 9 2 9 2 8 9 8 3 3 8 1 3 4 9 |
1 0 2 |
Birinchi misoldagi graf quyidagicha ko’rinishda:
1-so’rovda 3 va 8 tugunlar uchun yagona muhim tugun 1-tugun hisoblanadi.
2-so’rovda 1-va 3- tugunlar uchun birorta ham muhim tugun yo’q, grafdagi boshqa ixtiyoriy tugunni olib tashlasa ham bu tugunlar o’rtasida yo’l doim bo’ladi.
3-so’rovda 4- va 9- tugunlar uchun muhim tugunlar 3- va 1- tugunlardir.