Pengsoo là một chú chim cánh cụt khổng lồ nổi tiếng người Hàn Quốc. Chú rất thô lỗ và thích ca hát.

Lần này, Pengsoo đang thực hiện các truy vấn trên đồ thị.

Chú có một đồ thị vô hướng liên thông, trong đó mỗi đỉnh nằm trên tối đa $k$ chu trình đơn (vertex-simple cycles).

Chú muốn trả lời hai loại truy vấn:

• Đánh dấu một đỉnh $v$.
• Tìm đỉnh được đánh dấu gần nhất với đỉnh $v$ (đảm bảo rằng khi truy vấn loại này được đưa ra, luôn có ít nhất một đỉnh đã được đánh dấu).

Pengsoo rất lười biếng và đã quyết định đi ngủ, vì vậy chú yêu cầu bạn thực hiện các truy vấn này. Nếu bạn không hoàn thành kịp trước khi chú thức dậy, chú sẽ bắt nạt bạn, vì vậy hãy hành động nhanh chóng!

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào chứa ba số nguyên $n, m, k$ ($1 \le n \le 100\,000, n - 1 \le m \le 200\,000, 0 \le k \le 10$): số lượng đỉnh, số lượng cạnh và số lượng chu trình đơn lớn nhất có thể đi qua một đỉnh.

$m$ dòng tiếp theo chứa mô tả các cạnh. Dòng thứ $i$ chứa hai số nguyên $u_i, v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$), biểu thị một cạnh giữa hai đỉnh $u_i$ và $v_i$.

Đảm bảo rằng không có đa cạnh, đồ thị liên thông và mỗi đỉnh nằm trên tối đa $k$ chu trình đơn.

Dòng tiếp theo chứa một số nguyên $q$ ($1 \le q \le 200\,000$): số lượng truy vấn.

$q$ dòng tiếp theo chứa mô tả các truy vấn. Dòng thứ $i$ chứa hai số nguyên $t_i, v_i$ ($1 \le t_i \le 2, 1 \le v_i \le n$).

Nếu $t_i = 1$, đánh dấu đỉnh $v_i$. Đảm bảo rằng đỉnh này chưa được đánh dấu trước đó.

Nếu $t_i = 2$, tìm khoảng cách đến đỉnh được đánh dấu gần nhất từ $v_i$. Đảm bảo rằng luôn có ít nhất một đỉnh đã được đánh dấu.

Dữ liệu ra

Với mỗi truy vấn có $t_i = 2$, in ra khoảng cách đến đỉnh được đánh dấu gần nhất.

Ví dụ

Dữ liệu vào 1

5 4 0
1 2
2 3
3 4
4 5
7
1 1
1 5
2 1
2 2
2 3
2 4
2 5

Dữ liệu ra 1

0
1
2
1
0

Dữ liệu vào 2

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

Dữ liệu ra 2

2
2