Có một cây (đồ thị liên thông, vô hướng, không có chu trình) gồm $N$ đỉnh. Các đỉnh được đánh số từ $1$ đến $N$, các cạnh được đánh số từ $1$ đến $N-1$. Ban đầu, tất cả các đỉnh đều có màu trắng.

Hãy viết chương trình thực hiện hai loại truy vấn sau:

• 1 i: Đổi màu đỉnh $i$ (trắng $\rightarrow$ đen, đen $\rightarrow$ trắng).
• 2: Với mọi cặp đỉnh trắng $a$ và $b$, in ra khoảng cách lớn nhất. Ở đây, $a$ và $b$ có thể trùng nhau. Nếu không có đỉnh trắng nào, in ra $-1$.

Dữ liệu vào

Dòng đầu tiên chứa $N$ ($2 \le N \le 100\,000$).

$N-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $u$ và $v$ là hai đầu mút của cạnh thứ $i$, và độ dài $w$ của cạnh đó.

Dòng tiếp theo chứa số lượng truy vấn $M$ ($1 \le M \le 100\,000$).

$M$ dòng cuối cùng, mỗi dòng chứa một truy vấn.

Độ dài các cạnh luôn là số nguyên thỏa mãn lớn hơn hoặc bằng $-1\,000$ và nhỏ hơn hoặc bằng $1\,000$.

Dữ liệu ra

Với mỗi truy vấn loại $2$, in ra kết quả trên một dòng theo đúng thứ tự.

Ví dụ

Đầu vào 1

3
1 2 1
1 3 1
7
2
1 1
2
1 2
2
1 3
2

Đầu ra 1

2
2
0
-1