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