D. Усан мод

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

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

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

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

Галзуу эрдэмтэн Майк $n$ орой бүхий өлгөгдсөн мод байгуулсан байна. Орой болгон нь ус агуулах сав болох ба энэхүү сав нь усаар дүүрсэн эсхүл хоосон байж болно.

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

Майк дараах үйлдлүүдийг модонд хийхийг хүсч буй:

  1. $v$ оройг усаар дүүргэнэ. Дараа нь $v$ болон түүний бүх хүүхдийг нь усаар дүүрнэ.
  2. $v$ оройг хоослох. Дараа нь $v$ болоод түүний бүх эцэг орой нь хоосорно.
  3. Яг энэ мөчид тухайн орой $v$ усаар дүүрсэн байгаа эсэхийг тодорхойлох.

Модны бүх оройн анхны төлөв нь хоосон байх болно.

Майк аль хэдийн хүсэлтээс түүний гүйцэтгэхийг хүссэн үйлдлүүдийн дарааллыг хөрвүүлчихсэн байгаа. Модыг туршилтанд оруулахаас өмнө Майк загварчлагдсан жагсаалтыг ажиллуулахаар шийдсэн. Бүх үйлдлийг гүйцэтгэсний дараа ямар үр дүн гарахыг нь тодорхойлоход түүнд тусална уу.

Оролт

Эхний мөрөнд модны оройн тоог илэрхийлэх $n$ ($1 ≤ n ≤ 500000$) тоо өгөгдөнө. Дараагийн $n-1$ мөрөнд модны ирмэгийг илэрхийлэх $a_i, b_i$ ($1 ≤ a_i, b_i ≤ n$, $a_i ≠ b_i$) хоёр тоо зайгаар тусгаарлагдан өгөгдөнө.

Дараагийн мөрөнд гүйцэтгэх үйлдлүүдийг илэрхийлэх $q$ ($1 ≤ q ≤ 500000$) тоо өгөгдөнө. $q$ мөр тус бүрд $c_i$ ($1 ≤ c_i ≤ 3$), $v_i$ ($1 ≤ v_i ≤ n$) хоёр тоо зайгаар тусгаарлагдан өгөгдөнө. $c_i$ нь үйлдлийн төрөл (дээр өгөгдсөн үйлдлүүдийн дугаар) $v_i$ нь үйлдэл гүйцэтгэгдсэн орой болно.

Өгөгдсөн граф нь мод болох нь баталгаатай.

Гаралт

$3$ гэсэн үйлдэл тус бүрд хэрэв орой нь дүүрэн бол $1$ эсхүл хоосон бол $0$-ыг мөрөөр тусгаарлан хэвлэнэ үү. Оролтонд өгөгдсөн хүсэлтийн дарааллын дагуу хүсэлтийн хариуг нь хэвлээрэй.

Орчуулсан: Э.Шүрэнчулуун

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

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