Cho một đồ thị liên thông, vô hướng và có trọng số gồm ~n~ đỉnh và ~m~ cạnh.

Cho ~q~ truy vấn có dạng ~(e, c)~: Sau khi xóa cạnh thứ ~e~, có bao nhiêu đỉnh liên thông với đỉnh ~c~?

Dữ liệu đảm bảo mỗi cảnh bị xóa tối đa ~1~ lần.

Đầu vào

Dòng đầu tiên gồm ba số nguyên dương ~n~, ~m~, ~q~ ~(1 \le n, m, q \le 10^5)~.

~m~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~u, v~ biểu diễn có cạnh nối giữa hai đỉnh ~u~ và ~v~ ~(1 \le u, v \le n)~.

~q~ dòng tiếp theo, mỗi dòng là đầu vào của một truy vấn gồm hai số nguyên ~e, c~ ~(1 \le e \le m, 1 \le c \le n)~.

Đầu ra

In ra ~q~ dòng, dòng thứ ~i~ là kết quả của truy vấn thứ ~i~.

Ví dụ

Đầu vào

4 4 3
1 2
2 3
3 4
2 4
4 4
2 3
1 1

Đầu ra

4
2
1