Laiko ribojimas: 1.5s

Atminties ribojimas: 256MB

Duomenų failas: keliu_ilgiai.in

Rezultatų failas: keliu_ilgiai.out

Jei norite pateikti savo sprendimą - prisijunkite.

Kelių ilgiai

Baitlandijoje yra n miestų ir m abipusių kelių. Miestai yra sunumeruoti nuo 1 iki n. Kiekvienas kelias jungia du miestus. Tarp miestų važinėti galima tik juos jungiančiais keliais. Jums bus pateikta q užklausų, kurių kiekvienoje nurodyti du miestai. Reikia pasakyti, per kiek mažiausiai kelių reikia važiuoti, kad iš pirmojo iš šių miestų nuvažiuotume į antrąjį.

Pradiniai duomenys

Pirmoje eilutėje pateikti skaičiai n (1\\len\\le3000) ir m (0\\lem\\lemin(3000,\\frac{n\\times(n-1)}{2})) - miestų skaičius ir kelių skaičius. Kitose m eilučių pateikiami keliai. Kiekvienoje jų įrašyti skaičiai a ir b (1\\lea,b\\len) - pora miestų, kuriuos jungia kelias. Garantuojama, kad joks kelias nejungia miesto su pačiu savimi, bei jokios poros miestų nejungia daugiau nei vienas kelias. Tolimesnėje eilutėje nurodytas skaičius q (1\\leq\\le100000) - užklausų skaičius. Kitose q eilučių pateikiamos užklausos. Kiekvienoje jų įrašyti skaičiai x ir y - miestai, kuriems reikia pasakyti, kiek mažiausiai kelių reikia pervažiuoti, kad iš miesto x atvažiuotume į miestą y.

Išvestis

Reikia išvesti q eilučių - i-ojoje eilutėje turi būti atsakymas į i-ają užklausą. Jei iš vieno užklausoje pateikto miesto neįmanoma patekti į kitą, išveskite -1.

Pavyzdžiai

Duomenys Rezultatai 
5 5
1 2
2 3
3 4
4 1
1 5
5
1 3
3 5
4 5
2 3
1 1
 
2
3
2
1
0