7234번 - Unter 서브태스크다국어

Justas planuoja sukurti programėlę, leidžiančią žmonėms dalintis kelionėmis automobiliu. Pirmiausia jam reikia parašyti programą, kuri leistų rasti trumpiausią atstumą tarp dviejų namų.

Mieste, kuriame veiks programėlė, yra N namų, sunumeruotų nuo 1 iki N. Namus tiesiogiai jungia N dvikrypčių gatvių. Viena gatvė jungia lygiai du namus ir du namus jungia ne daugiau kaip viena gatvė.

Justas jau parašė algoritmą, kuris leidžia rasti trumpiausią kelią tarp dviejų namų, kai yra tik vienas būdas nuvažiuoti iš vieno namo į kitą, nevažiuojant pro tą patį namą daugiau nei kartą. Tačiau jam reikia jūsų pagalbos rasti trumpiausią kelią tarp tokių namų porų, tarp kurių nuvažiuoti yra daugiau nei vienas toks būdas.

Raskite trumpiausią atstumą tarp Q namų porų.

Pirmoje eilutėje pateikiami du sveikieji skaičiai: namų skaičius N ir užklausų skaičius Q.

Tolimesnėse N eilučių pateikiama po du tarpu atskirtus sveikuosius skaičius a_i ir b_i. Šie skaičiai nurodo, kad mieste egzistuoja gatvė tarp namų a_i ir b_i.

Likusiose Q eilučių pateikiama po du tarpu atskirtus sveikuosius skaičius c_j ir d_j.

Išveskite Q eilučių. k-toje eilutėje pateikite vieną skaičių – trumpiausio kelio tarp namų c_k ir d_k ilgį. Atstumą tarp dviejų namų Justas skaičiuoja kaip gatvių, kuriomis reikia važiuoti, skaičių.

• 3 ≤ N ≤ 200 000
• 1 ≤ a_i, b_i ≤ N (1 ≤ i ≤ N, a_i ≠ b_i)
• 1 ≤ Q ≤ 1 000 000
• 1 ≤ c_j, d_j ≤ N (1 ≤ j ≤ Q, c_j ≠ d_j).
• Iš c_j į d_j galima patekti daugiau nei vienu (nebūtinai trumpiausiu) keliu, kuris pro jokį namą neina daugiau negu vieną kartą.
• Iš bet kurio namo gatvėmis visada bus galima nukeliauti iki bet kurio kito namo.