$N$개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 $1$번부터 $N$번까지 번호가 매겨져 있고, 간선은 $1$번부터 $N-1$번까지 번호가 매겨져 있다. 가장 처음에 모든 정점의 색은 검정색이다.

아래의 두 쿼리를 수행하는 프로그램을 작성하시오.

• 1 i: $i$번 정점의 색을 바꾼다. (흰색 $\to$ 검정색, 검정색 $\to$ 흰색)
• 2 v: 모든 흰색 정점 $u$와 $v$까지의 거리 중에서 가장 가까운 거리를 출력한다. 이때, $u$와 $v$는 같아도 된다. $v$가 흰색이면 정답은 $0$이다. 트리에 흰색 정점이 없으면 $-1$을 출력한다.

입력

첫째 줄에 $N$ ($2 \le N \le 100{,}000$)이 주어진다.

둘째 줄부터 $N-1$개의 줄에는 $i$번 간선이 연결하는 두 정점 번호 $u$와 $v$가 주어진다.

다음 줄에는 쿼리의 개수 $M$ ($1 \le M \le 100{,}000$)이 주어진다.

다음 $M$개의 줄에는 쿼리가 한 줄에 하나씩 주어진다.

출력

각각의 $2$번 쿼리의 결과를 순서대로 한 줄에 하나씩 출력한다.

Sample

Input

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

Output

2
2
2
3
0