Дано дерево (связный граф без циклов) с $N$ вершинами. Вершины пронумерованы от $1$ до $N$, рёбра пронумерованы от $1$ до $N-1$. Изначально все вершины окрашены в чёрный цвет.

Напишите программу, которая выполняет следующие два типа запросов:

• 1 i: изменить цвет вершины $i$ (белый $\to$ чёрный, чёрный $\to$ белый).
• 2 u: подсчитать количество вершин $v$, связанных с $u$. Две вершины считаются связанными, если все вершины на пути между ними имеют одинаковый цвет.

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

Первая строка содержит $N$ ($2 \le N \le 100\,000$).

Каждая из следующих $N-1$ строк содержит два целых числа $u$ и $v$ — вершины, соединённые $i$-м ребром.

Следующая строка содержит количество запросов $M$ ($1 \le M \le 100\,000$).

Каждая из следующих $M$ строк содержит один запрос.

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

Для каждого запроса типа 2 выведите результат в отдельной строке в порядке их появления.

Примеры

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

5
1 2
1 3
1 4
1 5
3
2 1
1 1
2 1

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

5
1

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

7
1 2
1 3
2 4
2 5
3 6
3 7
4
2 1
1 1
2 2
2 3

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

7
3
3