D. Сахал граф

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

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

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

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

$n$ орой, $n-1$ ирмэгтэй, чиглэлгүй холбоост графын хамгийн ихдээ ганцхан орой нь $2$-оос их өнцөгтэй ба бусад орой нь $2$ эсвэл $1$ оройн өнцөгтэй байдаг бол тэр графыг сахал гэе. Мөн оройн өнцөг гэдгээр тухайн оройд хэдэн ирмэг холбогдож буйг илэрхийлдэгийг эргэн санаарай.

Бүх ирмэг зөвхөн хар эсвэл цагаан өнгөтэй байна. Эхэндээ бүх ирмэг хар өнгөтэй байна.

Танд сахал граф өгөгдсөн байгаа ба та дараах төрлийн хүсэлтүүдэд анализ хийх хэрэгтэй.

  • $i$-р ирмэгийг хараар буд. Ирмэгийн дугаар $i$ нь оролтонд өгөгдсөн байгаа ба энэ хүсэлт ирэх үед тухайн $i$-р ирмэг цагаан өнгөтэй байна.
  • $i$-р ирмэгийг цагаанаар буд. Энэ хүсэлт ирэх үед тухайн $i$-р ирмэг хар өнгөтэй байна.
  • $a$ оройгоос $b$ оройруу зөвхөн хар ирмэгүүдээр дамжин очих хамгийн богино замын уртыг олох эсвэл тийм зам байхгүй гэдгийг илэрхийлэх(замын урт гэдэг нь тэр замд буй ирмэгийн тоонууд)

Оройнууд $1$-с $n$ хүртэл дугаарлагдсан ба ирмэгүүд $1$-с $n-1$ хүртэл дугаарлагдсан.

Оролт

Эхний мөрөнд бүхэл тоо $n$ ($2 ≤ n ≤ 10^5$) байх ба энэ нь граф дахь оройн тоонууд. Дараагийн $n-1$ мөрөнд $v_i$, $u_i$ ($1 ≤ v_i, u_i ≤ n$, $v_i ≠ u_i$) гэсэн хоёр оройгоор илэрхийлэгдэх ирмэгийн мэдээллүүд байрлана. Өгөгдсөн граф нь холбоост, сахал байх ба дотроо цикл үүсгэдэггүй байна гэдэгт итгэлтэй байж болно.

Дараагийн мөр нь хүсэлтүүдийн тоо болох $m$ ($1 ≤ m ≤ 3·10^5$)-ийг агуулах ба дараагийн $m$ мөрөнд хүсэлтүүд байрлах ба хүсэлт нь эхлээд $type$ (хүсэлтийн төрлийг илэрхийлнэ 1-ээс 3 хүртэлх утгуудтай) дараа $type$-аасаа хамаарсан мэдээлэлтэй байна.

  • хэрэв $type = 1$ бол энэ хүсэлт ямар нэгэн ирмэгийг хараар будах хүсэлт бөгөөд будах ирмэгийн дугаар $id$ ($1 ≤ id ≤ n-1$) ард нь байрлана.
  • хэрэв $type = 2$ бол энэ хүсэлт нь ямар нэгэн ирмэгийг цагаанаар будах хүсэлт бөгөөд будах цагаанаар ирмэгийн дугаар $id$ ($1 ≤ id ≤ n - 1$) ард нь байрлана.
  • хэрэв $type = 3$ бол энэ нь $a$, $b$ ($1 ≤ a, b ≤ n$, a,b нь тэнцүү байж болно) оройнуудын хоорондох хамгийн богино замыг олох хүсэлт юм.

Дараагийн мөр нь хүсэлтүүдийн тоо болох $m$ ($1 ≤ m ≤ 3·10^5$)-ийг агуулах ба дараагийн $m$ мөрөнд хүсэлтүүд нь эхлээд $type$ (хүсэлтийн төрлийг илэрхийлнэ, 1-ээс 3 хүртэлх утгуудтай) дараа $type$-аасаа хамаарсан мэдээлэлтэй байна.

Оролтын мөрнүүд дэх тоонууд яг нэг хоосон зайгаар тусгаарлагдсан ба ирмэгүүдийн дугаар нь оролтод байсантайгаа ижил.

Гаралт

"а болон b орой хоорондын хамгийн богино замыг олох" хүсэлт бүрд хариу хэвлэх ба $a$ болон $b$ орой хоёрын хооронд зам байхгүй бол "-1" хэвлэнэ. Хариунуудыг орж ирсэн хүсэлтийнх дарааллаар хэвлэх ба тоонуудыг хооронд хоосон зай эсвэл мөр шилжүүлэлтээр тусгаарлана.

Орчуулсан: mmur

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

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

Тэмдэглэл

In the first sample vertices $1$ and $2$ are connected with edge number $1$, and vertices $2$ and $3$ are connected with edge number $2$. Before the repainting edge number $2$ each vertex is reachable from each one along the black edges. Specifically, the shortest path between $1$ and $3$ goes along both edges.

If we paint edge number $2$ white, vertex $3$ will end up cut off from other vertices, that is, no path exists from it to any other vertex along the black edges.

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