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

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

• 1 i: изменить цвет вершины $i$ (белый → чёрный, чёрный → белый).
• 2 v: вывести номер первой чёрной вершины на пути от вершины $1$ до вершины $v$. Если такой вершины нет, выведите $-1$.

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

В первой строке задано $N$ ($2 \le N \le 100\,000$).

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

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

В следующих $M$ строках записаны сами запросы, по одному на строке.

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

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

Примеры

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

9
1 2
1 3
2 4
2 9
5 9
7 9
8 9
6 8
8
2 3
1 8
2 6
2 7
1 2
2 9
1 2
2 9

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

-1
8
-1
2
-1