E. Ксэния ба мод

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

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

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

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

Програмист Ксэнияд $n$ зангилаанаас бүрдсэн мод байна. Бид модны зангилаануудыг 1-ээс $n$ хүртэл дугаарлагдсан ба эхэндээ нэгдүгээр зангилаа улаанаар, бусад зангилаа цэнхэрээр будагдсан гэж үзнэ.

Модны $v$ ба $u$ зангилаануудын хоорондох зай нь $v$ ба $u$-н хоорондох хамгийн богино замын ирмэгүүдийн тоо юм.

Ксения хурдан хоёр төрлийн асуулгыг гүйцэтгэх талаар суралцах хэрэгтэй:

  1. өгөгдсөн цэнхэр зангилааг улаанаар будна;
  2. өгөгдсөн зангилаанаас хамгийн ойрын улаан зангилааг тооцоолох ба хамгийн ойрын улаан зангилаа хүртэлх хамгийн богино зайг хэвлэнэ.

Таны даалгавар бол тодорхойлсон асуулгыг гүйцэтгэх програм бичих явдал юм.

Оролт

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

Дараагийн $m$ мөрүүд асуулгууд байна. Асуулга бүр нь $t_{i}, v_{i}$ $(1 ≤ t_{i} ≤ 2, 1 ≤ v_{i} ≤ n)$ бүхэл тоон хосоор өгөгдөнө. Хэрвээ$t_{i} = 1$ бол бид асуулгын хариунд $v_{i}$ цэнхэр зангилааг улаанаар будах хэрэгтэй. Хэрвээ $t_{i} = 2$ бол асуулгын хариунд ямар нэг улаан зангилаанаас $v_{i}$ зангилаа хүрэх хамгийн богино замыг хэвлэх ёстой.

Өгөгдсөн граф нь мод бөгөөд бүх асуулгууд зөв гэдэг нь баталгаатай.

Гаралт

Хоёр дахь төрлийн асуулга бүрийн хариуг нэг мөрөнд хэвлэнэ.

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

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

Оролт
5 4
1 2
2 3
2 4
4 5
2 1
2 5
1 2
2 5
Гаралт
0
3
2
Сэтгэгдлүүдийг ачааллаж байна...