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