407715: GYM102881 D YSYS

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.

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.

Print the number of cities where the headquarters could be.

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

3

5 5 3
1 2
2 3
3 4
4 5
1 5
7 1
77 2
777 3

5

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