Yassora the terrorist was on a wild run in Pillowoslovakia. Pillowoslovakia is a country that consists of some cities connected by bi-directional roads. Yassora's group has its headquarters in some unknown (yet) city. Enter Pillow Holmes to save the day.
Pillow Holmes knows the following about Yassora's movements:
Pillow Holmes gave you a log of the bombings that Yassora orchestrated. Each event in that log consists of a day and a city. An event $b o m b (d, c)$ means that a bomb that Yassora had planted a bomb in city $c$ on day $d$ *or an earlier day*, and it exploded on day $d$.
Pillow Holmes has also exploited the following technical difficulty in YSYS:
Now, Pillow Holmes gave you the log of the bombings sorted in chronological order (sorted by day). He wants to know the number of possible cities the headquarters could exist. Remember that Yassora is in the headquarters on day 0.
The first line contains 3 integers $n$, $m$, and $q$ $(2 <= n <= 2000,$ $1 <= m <= 10^4,$ $1 <= q <= 10^6)$ — the number of cities, the number of roads, and the number of entries in the log respectively.
The following $m$ lines contains the description of a road each, in the format $u$ $v$ $(1 <= u, v <= n)$ — the two cities connected by this road.
The following $q$ lines contains two integers each $d$ and $c$ $(1 <= d <= 10^7,$ $1 <= c <= n)$ — which means that a bomb exploded on day $d$ in city $c$.
It's guaranteed that Pillowoslovakia has no self-roads or multiple roads between the same pair of cities.
Print the number of cities where the headquarters could be.
In the first sample, the cities where the headquarters could have been are 1, 2, and 3.
## Input
The first line contains 3 integers $n$, $m$, and $q$ $(2 <= n <= 2000,$ $1 <= m <= 10^4,$ $1 <= q <= 10^6)$ — the number of cities, the number of roads, and the number of entries in the log respectively.The following $m$ lines contains the description of a road each, in the format $u$ $v$ $(1 <= u, v <= n)$ — the two cities connected by this road.The following $q$ lines contains two integers each $d$ and $c$ $(1 <= d <= 10^7,$ $1 <= c <= n)$ — which means that a bomb exploded on day $d$ in city $c$.It's guaranteed that Pillowoslovakia has no self-roads or multiple roads between the same pair of cities.
## Output
Print the number of cities where the headquarters could be.
[samples]
## Note
In the first sample, the cities where the headquarters could have been are 1, 2, and 3.
**Definitions**
Let $ n, t, x, k \in \mathbb{Z}^+ $:
- $ n $: number of problems,
- $ t $: total contest time,
- $ x $: time to read and initially "solve" a problem,
- $ k $: penalty per wrong submission.
Let $ A = (a_1, a_2, \dots, a_n) \in \mathbb{Z}^n $, where $ a_i $ is the debug time for problem $ i $.
Each problem $ i $ has two possible outcomes:
- **Case 1 (Read error)**: Total time = $ x + a_i $, penalty contribution = $ x + a_i $ (no wrong submissions).
- **Case 2 (Bug / WA)**: Total time = $ x + k + a_i $, penalty contribution = $ x + k + a_i $ (one wrong submission).
Let $ S \subseteq \{1, 2, \dots, n\} $ be the set of solved problems, and $ \sigma $ a permutation of $ S $ representing the order of submission.
For a given $ S $ and $ \sigma $, the total time is:
$$
T_{\text{total}} = \sum_{j=1}^{|S|} \left( x + \delta_j + a_{\sigma(j)} \right)
$$
where $ \delta_j = 0 $ if problem $ \sigma(j) $ had a read error, $ \delta_j = k $ if it had a WA.
The penalty is:
$$
P = \sum_{j=1}^{|S|} \left( \sum_{\ell=1}^{j} (x + \delta_\ell + a_{\sigma(\ell)}) \right)
$$
**Constraints**
1. $ 1 \le n \le 10^5 $
2. $ 1 \le t \le 10^{13} $
3. $ 1 \le x, k \le 10^8 $
4. $ 1 \le a_i \le 2 \times 10^8 $
5. $ T_{\text{total}} \le t $
**Objective**
Maximize $ m = |S| $, the number of solved problems.
Among all $ (S, \sigma) $ achieving maximum $ m $, minimize the penalty $ P $.