D. YSYS
time limit per test
2 seconds
memory limit per test
256 megabytes
input
ysys.in
output
standard output

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:

  • On day 0, he's in the headquarters.
  • If on the $$$i^{th}$$$ day he's in city $$$u$$$. Then, on the $$$(i+1)^{th}$$$ day, he'll be in city $$$u$$$ or a city $$$v$$$ connected to it by a road. In other words: everyday, he either stays put or moves along one road.
  • He plants bombs as he moves, and he detonates them later.

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 $$$bomb(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:

  • The bombs explode in the same order they were planted by Yassora. In other words: if he plants a bomb $$$a$$$ and then another bomb $$$b$$$, he must detonate bomb $$$a$$$ before bomb $$$b$$$.

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.

Input

The first line contains 3 integers $$$n$$$, $$$m$$$, and $$$q$$$ $$$(2 \leq n \leq 2000,$$$ $$$1 \leq m \leq 10 ^ 4,$$$ $$$1 \leq q \leq 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 \leq u, v \leq n)$$$ — the two cities connected by this road.

The following $$$q$$$ lines contains two integers each $$$d$$$ and $$$c$$$ $$$(1 \leq d \leq 10^7,$$$ $$$1 \leq c \leq 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.

Examples
Input
5 4 4
1 2
1 3
2 4
2 5
2 3
4 1
5 3
7 4
Output
3
Input
5 5 3
1 2
2 3
3 4
4 5
1 5
7 1
77 2
777 3
Output
5
Note

In the first sample, the cities where the headquarters could have been are 1, 2, and 3.