D. Водяное дерево
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Безумный ученый Майк построил корневое дерево, которое состоит из n вершин. Каждая вершина представляет собой резервуар, который может быть либо пуст, либо заполнен водой.

Вершины дерева пронумерованы числами от 1 до n. Корень дерева находится в вершине 1. Резервуары детей каждой вершины расположены ниже резервуара этой вершины, при этом вершина соединена с каждым из детей трубой, по которой вниз может стекать вода.

Майк хочет выполнять с деревом следующие операции:

  1. Заполнить водой вершину v. Тогда v и все ее потомки (дети, дети детей, и так далее) заполняются водой.
  2. Опустошить вершину v. Тогда v и все ее предки становятся пустыми.
  3. Определить, заполнена ли вершина v водой в данный момент.

Изначально все вершины дерева пусты.

Майк уже составил полный список операций, которые он хочет выполнить по порядку. Перед испытанием дерева Майк решил провести симуляцию этих действий. Помогите Майку определить, какие результаты он получит в результате выполнения всех операций.

Входные данные

В первой строке входных данных записано целое число n (1 ≤ n ≤ 500000) — количество вершин в дереве. В каждой из следующих n - 1 строк через пробел записаны по два целых числа ai, bi (1 ≤ ai, bi ≤ n, ai ≠ bi) — ребра дерева.

В следующей строке дано целое число q (1 ≤ q ≤ 500000) — количество операций. В каждой из следующих q строк через пробел записано по два целых числа ci (1 ≤ ci ≤ 3), vi (1 ≤ vi ≤ n), где ci обозначает номер типа операции (согласно нумерации в условии), а vi обозначает вершину, над которой проводится операция.

Гарантируется, что данный граф является деревом.

Выходные данные

Для каждой операции типа 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