Given a connected, undirected graph of $n$ vertices and $m$ edges.
There are $q$ queries, each of the form $(e, c)$. After removing the $e^{th}$ edge, how many vertices are in the same connected component with $c$. It is guaranteed that each edge is removed at most one time.
### Input
- The first line contain 3 integers $n, m, q$.
- The next $m$ lines, each line contains 2 integers $u, v$, there is an edge between $u, v$.
- The next $q$ lines, each line contains 2 integers $e, c$, a query.
### Output
- Print $q$ lines, the $i^{th}$ is the answer to query $i$.
### Constraints
- $1 \le n, m, q \le 10^5$.
- $1 \le u, v \le n$.
- $1 \le e \le m$.
- $1 \le c \le n$.
### Example
Input:
```
4 4 3
1 2
2 3
3 4
2 4
4 4
2 3
1 1
```
Output:
```
4
2
1
```
