G. Шинэ жилийн гүйлт

хугацааны хязгаарлалт 4 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

"Мод" арлын шинэ жил удахгүй болох гэж байна. Нэрнээс нь харахад энэ арал нь $n - 1$ ширхэг замаар холбогдсон $n$ хотуудтай ба аль ч хоёр ялгаатай хотын хооронд тэдгээрийг холбосон нэг зам үргэлж байдаг. "Мод" арлын хүн бүр нэг замаар явахад яг нэг минут зарцуулдаг.

"Мод" арлын гүйгчдэд "өөрийгөө сорих гүйлт" гэж нэрлэгддэг их хачирхалтай шинэ жилийн уламжлал байдаг. Энэ уламжлалаа дараах байдлаар хийдэг.

Гүйгч $a$ ба $b$ гэсэн ялгаатай хоёр хот сонгоно. Энгийн болгох үүднээс $a$ хотоос $b$ хот хүрэх хамгийн богино замыг $p_{1}, p_{2}, ..., p_{l}$ (энд $p_{1} = a$ ба $p_{l} = b$ байна) гэж илэрхийлье. Үүний дараа:

  1. Гүйгч $a$ хотоос эхэлнэ.
  2. Гүйгч $a$ хотоос $b$ хот хүрэх хамгийн богино замыг даган $a$ хотоос $b$ хот руу гүйнэ.
  3. Гүйгч $b$ хотод ирмэгцээ тэр даруй $b$ хотоос $a$ хот хүрэх хамгийн богино замаар буцаж $a$ хот руу гүйнэ.
  4. Гүйгч $a$ хотод ирмэгцээ тэр даруй $a$ хотоос $b$ хот хүрэх хамгийн богино замаар буцаж $b$ хот руу гүйнэ.
  5. 3 ба 4-р алхамуудыг тасралтгүй давтана.

Товчоор хэлбэл, гүйгчийн замыг дараах байдлаар илэрхийлж болно:

$$ p_1 → p_2 → ... → p_{l-1} → p_{l} → p_{l-1} → ... → p_2 → p_1 → p_2 → ... $$

Шинэ жилийн баяраа тэмдэглэхийн тулд JH ба JY хэмээх хоёр гүйгч "өөрийгөө сорих гүйлт" хийхээр шийджээ. JH нь $u$ ба $v$ гэсэн хоёр хот сонгосон бол JY нь $x$ ба $y$ гэсэн хоёр хот сонгожээ. Тэд зэрэг гүйж эхлэх ба ижил хотод уулзах хүртлээ гүйхээр шийджээ. Тэдний хувьд зам дээр таарах нь тийм ч чухал биш юм. Гүйж эхлэхээсээ өмнө тэд өөрсдийн гүйх хугацаагаа мэдэхийг хүсэж байна.

Үүнийг тооцоолох нь JH, JY хоёрт их хэцүү байгаа тул тэд танаас тусламж хүсэж байна.

Оролт

Эхний мөрөнд "Мод" арлын хотуудын тоо болох $n$ ($5 ≤ n ≤ 2 × 10^{5}$) гэсэн эерэг бүхэл тоог оруулна.

Дараагийн $n - 1$ мөрөнд "Мод" арлын замуудыг тодорхойлсон байна. $i$-р ($1 ≤ i ≤ n - 1$) мөр нь зайгаар тусгаарлагдсан $a_{i}$ ба $b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n, a_{i} ≠ b_{i}$) бүхэл тоонуудыг агуулна. Эдгээр нь модны нэг замаар холбогдсон оройнууд юм.

Дараагийн мөр нь асуултуудын тоо болох $t$ ($1 ≤ t ≤ 2 × 10^{5}$) бүхэл тоог агуулна.

Дараагийн $t$ мөрүүд нь хүсэлтүүдийн тодорхойлолтыг агуулна. $j$-р ($1 ≤ j ≤ t$) мөрөнд зайгаар тусгаарлагдсан $u_{j}, v_{j}, x_{j}, y_{j}$ ($1 ≤ u_{j}, v_{j}, x_{j}, y_{j} ≤ n, u_{j} ≠ v_{j}, x_{j} ≠ y_{j}$) гэсэн дөрвөн бүхэл тоо байна. Энэ хүсэлтийн хувьд JH $u_{j}$ ба $v_{j}$ хоёр хот, JY $x_{j}$ ба $y_{j}$ хоёр хот сонгосон гэсэн утгатай. JH нь $u_{j}$ хотоос эхэлж гүйх ба JY нь $x_{j}$ хотоос эхэлж гүйнэ.

Гаралт

Хүсэлт бүрийн хувьд тэдний гүйх ёстой минутыг тодорхойлсон нэг бүхэл тоо хэвлэнэ. Хэрвээ тэд төгсгөлгүй удаан гүйх бол (өөрөөр хэлбэл тэд хэзээ ч ижил хотод уулзахгүй бол) "-1" гэж хэвлэнэ. Анхнаасаа нэг хотоос эхлэх бол "0" гэж хэвлэнэ.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
7
1 3
3 6
7 4
3 7
5 4
7 2
4
6 5 5 3
3 5 4 6
1 5 1 3
1 5 3 1
Гаралт
2
1
0
-1

Тэмдэглэл

Жишээ иймэрхүү харагдана:

Сэтгэгдлүүдийг ачааллаж байна...