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 dạng \((e,c)\). Sau khi xóa cạnh thứ \(e\), có bao nhiêu đỉnh còn liên thông với đỉnh \(c\). Dữ kiện đảm bảo mỗi cạnh bị xóa tối đa \(1\) lần

Ràng buộc

• \(1 \le n,m,q \le 10^5\)
• \(1 \le u,v \le n\)
• \(1 \le c \le n\)
• \(1 \le e \le m\)

Dữ liệu vào

• Dòng đầu tiên gồm \(3\) số nguyên \(n,m,q\).
• \(m\) dòng tiếp theo, mỗi dòng gồm \(2\) số nguyên \(u,v\), có cạnh nối giữa \(u\) và \(v\).
• \(q\) dòng tiếp theo, mỗi dòng gồm \(2\) số nguyên \(e,c\), một truy vấn.

Dữ liệu ra

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

Input 1

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

Output 1

4
2
1