Masala #0673

Xotira 64 MB Vaqt 1000 ms Qiyinchiligi 46 %
3.3 (Baholar 3)
14

  

Muhim tugunlar #5

NN ta tugun va MM ta qirradan iborat bog’langan yo’nalmagan graf berilgan. Ya’ni graf qirralari ikki tomonlamali hamda grafdagi ixtiyoriy tugundan boshqasiga qirralar orqali borish mumkin.

xx va yy tugunlar (xy)(x \ne y) uchun muhim tugun deb shunaqangi uu tugunga aytiladiki (ux,uy)(u \ne x, u \ne y), agar shu uu tugun grafdan olib tashlansa, grafda xx dan yy ga borishni imkoni bo’lmay qolsin.

Sizga qq ta so’rovlar orqali xx va yy tugunlar juftliklari beriladi, har bir so’rovdagi juftlik uchun muhim tugunlar sonini chiqaring.


Kiruvchi ma'lumotlar:

Birinchi qatorda ikkita butun son tugunlar soni nn va qirralar soni mm kiritiladi (3n,m105)(3 ≤ n, m ≤ 10^5). Keyingi mm ta qatorda graf qirralari uu va vv sonlar juftligi ko’rinishida beriladi (1u,vn,uv)(1 ≤ u, v ≤ n, u \ne v).

Keyingi qatorda so’rovlar soni qq beriladi (1q105)(1 ≤ q ≤ 10^5). Keyingi qq ta qatorda so’rovlarni ifodalovchi xx va yy sonlar juftligi beriladi (1x,yn,xy)(1 ≤ x, y ≤ n, x \ne y).

1-subtask (11 ball): n,m,q300n, m, q ≤ 300.
2-subtask (9 ball): Graf to’g’ri chiziq shaklida, ya’ni har bir tugunni bitta yoki ikkita qo’shnisi bo’lishi mumkin (m=n1m = n - 1 va n,q105n, q ≤ 10^5).
3-subtask (13 ball): m=n1m = n - 1 hamda har bir i2+1ni*2+1 ≤ n bo’lgan ii-tugundan i2i*2 va i2+1i*2+1 tugunlarga qirra mavjud (m=n1m = n - 1 va n,q105n, q ≤ 10^5).
4-subtask (21 ball): m=n1m = n - 1 va n,q105n, q ≤ 10^5
5-subtask (46 ball): n,m,q105n, m, q ≤ 10^5


Chiquvchi ma'lumotlar:

Har bir so’rov uchun xx va yy tugunlar juftligiga nisbatan muhim bo’lgan tugunlar sonini chiqaring.


Misollar
# 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
Izoh:

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.

Yechimini yuborish
Bu amalni bajarish uchun tizimga kiring, agar profilingiz bo'lmasa istalgan payt ro'yxatdan o'tishingiz mumkin