A country can be represented as a graph of $n$ vertices and $m$ edges, each vertex is a city.
The government wants to build $k$ power plant. The $i^{th}$ power plant is going to be built at city $A_i$ and has the radius of $R_i$ (cities having distance to $A_i$ no more than $R_i$ receive power from this plant).
The government now wants to know how many cities have access to power.
### Input
- The first line contains 3 integers $n, m, k$.
- The next $m$ lines, each line contains 2 integers $u, v$, there is an edge between $u$ and $v$.
- The next $k$ lines, $i^{th}$ line contains 2 integers $A_i, R_i$.
### Output
- Print the number of cities having access to power.
### Constraints
- $1 \le n, m,k \le 10^5$.
- $1 \le u, v, A_i, R_i \le n$.
### Example
Input:
```
6 5 2
1 2
1 3
3 4
3 5
2 6
1 1
6 2
```
Output:
```
4
```
