E. Кайса ба мод

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

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

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

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

Кайса ѳнѳѳдѳр гэртээ ѳнжиж байгаа бѳгѳѳд хүү нь түүнд зориулж энгийн даалгавар бэлдсэн байв.

$n$ оройтой, оройнууд нь $1$-ээс $n$ хүртэл дугаарлагдсан үндэстэй мод ѳгѳгдсѳн ($1$ орой нь үндэс). Модны орой бүр утгатай. $q$ хүсэлтэд хариулах хэрэгтэй. Хүсэлт бүр дараах хэлбэрүүдийн аль нэг хэлбэртэй байна:

  • Хүсэлт "1 $v$". Үндэснээс $v$ орой хүртэлх замыг бичье: $u_{1}, u_{2}, ..., u_{k}$ $(u_{1} = 1; u_{k} = v)$. $ХИЕХ(u_{i}\ оройн\ утга, v\ оройн\ утга) > 1$ ба $i < k$ байх $u_i$ оройг буцаах хэрэгтэй. Хэрвээ ийм $u_{i}$ орой хэд хэд байгаа бол $i$ тоо хамгийн их байх оройг буцаана. Тийм орой байхгүй бол $-1$ гэж буцаа.
  • Хүсэлт "2 $v$ $w$" хэлбэртэй байна. $v$ оройн утгыг $w$ болгоно.

Бүх хүсэлт ѳгѳгдсѳн бол Кайсад бодлогоо бодоход нь туслана уу.

Оролт

Эхний мѳр $n$, $q$ $(1 ≤ n, q ≤ 10^{5})$ бүхэл тоонуудыг зайгаар тусгаарлан агуулна.

Хоёрдугаар мѳр $n$ бүхэл тоо $a_{1}, a_{2}, ..., a_{n}$ $(1 ≤ a_{i} ≤ 2*10^{6})$ агуулна, энд $a_{i}$ нь $i$ оройн утгыг илэрхийлнэ.

Дараагийн $n - 1$ мѳр тус бүр $x_{i}$, $y_{i}$ $(1 ≤ x_{i}, y_{i} ≤ n; x_{i} ≠ y_{i})$ бүхэл тоонуудыг агуулна, энэ нь $x_{i}$, $y_{i}$ оройнууд ирмэгээр холбогдсоныг илэрхийлнэ.

Дараагийн $q$ мѳр бүр дээр ѳгѳгдсѳн аль нэг хэлбэртэй хүсэлтийг агуулна. Хүсэлт бүрийн хувьд дараах тэнцэтгэл биш биелнэ: $1 ≤ v ≤ n$, $1 ≤ w ≤ 2*10^{6}$. Оройн утгыг ѳѳрчлѳх хүсэлт $50$-иас хэтрэхгүйг анхаарна уу.

Гаралт

Нэгдүгээр тѳрлийн хүсэлт бүрийн хариуг буцаана уу.

Орчуулсан: Sugardorj

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

Оролт
4 6
10 8 4 3
1 2
2 3
3 4
1 1
1 2
1 3
1 4
2 1 9
1 4
Гаралт
-1
1
2
-1
1

Тэмдэглэл

$ХИЕХ(x, y)$ нь $x$, $y$ тоонуудын хамгийн их ерѳнхий хуваагч.

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