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

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

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

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

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

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

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

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

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

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

Примеры

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

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

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

2
2
2
3
0