#### Registered Users Only

Please login to view and utilize this feature.

## Problem Description

The city of Catville has come under attack! The structure of Catville can be described as a series of *N* intersections, with *E* roads, and each road *i* connecting two intersections *S _{i}* and

*T*.

_{i}A total of *B* bombs have been dropped on Catville, and the *i*th bomb has been dropped at intersection *X _{i}* with a power of

*Y*. The power of a bomb decides the extent of damage it can cause. A power 1 bomb will only damage the intersection it lands on, a power 2 bomb will damage the intersection it lands on as well as its neighbours, and so on. In general, a power

_{i}*x*bomb will damage all intersections that are reachable from

*X*with less than

_{i}*x*roads.

After the attack, the mayor of Catville wants to know, how many intersections of Catville have been damaged.

## Input

The first line of input will contain three integers, *N*, *E* and *B*.

The next *E* lines of input will contain two integers each, *S _{i}* and

*T*.

_{i}The next *B* lines of input will contain two integers each, *X _{i}* and

*Y*.

_{i}## Output

The output should contain one line with one integer, the number of damaged intersections.

## Limits

For all subtasks: 1 ≤ B ≤ N ≤ 500 000, 1 ≤ E ≤ 1 000 000, 1 ≤ S_{i}, T_{i}, X_{i} ≤ N, 1 ≤ Y_{i} < N. No two bombs will fall on the same spot.

Subtask 1 (3%): Y_{i} = 1.

Subtask 2 (9%): 1 ≤ N ≤ 1 000, E = N - 1, S_{i} = i, T_{i} = i + 1.

Subtask 3 (15%): 1 ≤ N ≤ 1 000, 1 ≤ E ≤ 2 000.

Subtask 4 (18%): B = 1.

Subtask 5 (11%): E = N - 1, S_{i} = i, T_{i} = i + 1.

Subtask 6 (10%): E = N, S_{i} = i, T_{i} = i % N + 1.

Subtask 7 (13%): 1 ≤ N ≤ 100 000, 1 ≤ E ≤ 200 000.

Subtask 8 (21%): No additional constraints.

Subtask 9 (0%): Sample Testcases.

## Sample Input 1

6 6 2 1 2 2 3 2 4 3 5 4 6 5 6 3 2 5 2

## Sample Output 1

4

## Sample Input 2

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

## Sample Output 2

4

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 3 | 20 | 1.5s | 256MB | Minimum |

2 | 9 | 21 | 1.5s | 256MB | Minimum |

3 | 15 | 42 | 1.5s | 256MB | Minimum |

4 | 18 | 20 | 1.5s | 256MB | Minimum |

5 | 11 | 41 | 1.5s | 256MB | Minimum |

6 | 10 | 20 | 1.5s | 256MB | Minimum |

7 | 13 | 62 | 1.5s | 256MB | Minimum |

8 | 21 | 162 | 1.5s | 256MB | Minimum |

9 | 0 | 2 | 1.5s | 256MB | Minimum |

### Judge Compile Command

g++ ans.cpp -o bombing -Wall -static -O2 -lm -m64 -s -w -std=gnu++14 -fmax-errors=512