E. Соёл иргэншил

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

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

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

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

Эндрю "соёл иргэншил" гэдэг тоглоом тоглодог бөгөөд Дима түүнд тусална.

Тоглоомонд $n$ хотууд болон $m$ хоёр чиглэлтэй замууд байдаг. Хотууд нь $1$-ээс $n$ хүртэл дугаарлагдсан. Аль ч хоёр хотуудын хооронд нэг (ганц) зам байдаг эсвэл ямар ч замгүй байдаг. Зам нь $v_{1}, v_{2}, ..., v_{k}$ ялгаатай хотуудын дараалал бөгөөд зэргэлдээх $v_{i}$ ба $v_{i + 1}$ ($1 ≤ i < k$) хотуудын хооронд зам байдаг. Тодорхойлсон чиглэлийн урт нь $(k - 1)$ байна. Хэрвээ хоёр хот чиглэлээр холбогдсон бол бид тэдгээр хотуудыг нэг бүс нутагт оршдог гэж үзнэ.

Тоглоомын туршид хоёр төрлийн үйлдлээр явагдана:

  1. Эндрю Димагаас $x$ хот оршдог бүс нутгийн хамгийн урт чиглэлийн уртын талаар асууна.
  2. Эндрю Димагаас $x$ хот оршдог бүс нутгийг $y$ хот оршдог бүс нутагтай нэгтгэхийг асууна. Хэрвээ хотууд нэг бүс нутагт оршдог бол нэгтгэх шаардлагагүй. Өөрөөр хэлвэл та дараах бүс нутгуудыг нэгтгэх хэрэгтэй: үр дүнд нь үүссэн бүс нутгын хамгийн урт чиглэлийн уртыг багасгах зорилгоор эхний бүс нутгаас хот сонгоно, хоёр дахь бүс нутгаас хот сонгоод тэдгээрийг замаар холбоно. Ийм хэд хэдэн арга байгаа бол та тэдгээрийн аль нэгийг сонгож болно.

Эндрюгийн асуулгыг гүйцэтгэхэд Димад хэцүү байгаа, тиймээс тэр танаас тусламж хүсэж байна. Димад тусал.

Оролт

Эхний мөр нь $n$, $m$, $q$ ($1 ≤ n ≤ 3*10^{5}$; $0 ≤ m < n$; $1 ≤ q ≤ 3*10^{5}$) гурван бүхэл тоог агуулна. Эдгээр нь харгалзан хотуудын тоо, замын тоо, болон асуулгын тоо юм.

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

Дараагийн $q$ мөр бүр нь дараах хэлбэрээр хоёр үйл явдлын нэгийг нь агуулна:

  • $1$ $x_{i}$. Энэ нь Эндрю Димад $x_{i}$ ($1 ≤ x_{i} ≤ n$) хотыг агуулсан бүс нутгын хамгийн урт чиглэлийн уртыг олох хүсэлт өгсөн гэсэн үг.
  • $2$ $x_{i}$ $y_{i}$. Энэ нь Эндрю Димад $x_{i}$ хотыг агуулсан бүс нутгыг $y_{i}$ ($1 ≤ x_{i}, y_{i} ≤ n$) хотыг агуулсан бүс нутагтай нэгтгэх хүсэлт өгсөн гэсэн үг. $x_{i}$ нь $y_{i}$-тэй тэнцүү байж болохыг анхаараарай.

Гаралт

Нэгдүгээр төрлийн үйлдэл бүрийн хариултыг тусдаа мөрөнд хэвлэнэ.

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

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

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