Cow Picnic

Interview

Time limit1sMemory limit128 MB

Summary

Given K starting pastures and a directed graph, count the pastures reachable from every one of the K starting positions.

Level: Medium4 of 10
Topics: Graph, DFS, BFS, Implementation
Solved: No attempts yet

Problem

The cows are having a picnic! Each of Farmer John's K cows (1 ≤ K ≤ 100) is grazing in one of N pastures (1 ≤ N ≤ 1,000), conveniently numbered 1 through N. The pastures are connected by M (1 ≤ M ≤ 10,000) one-way paths, and no path connects a pasture to itself.

The cows want to gather in the same pasture for their picnic, but because the paths are one-way, some cows may only be able to reach certain pastures. Determine how many pastures are reachable by every cow, and hence are possible picnic locations.

Input

Line 1: Three space-separated integers K, N, and M.
Lines 2 to K+1: Line i+1 contains a single integer (from 1 to N), the number of the pasture in which cow i is grazing.
Lines K+2 to M+K+1: Each line contains two space-separated integers A and B (both from 1 to N, with A ≠ B), representing a one-way path from pasture A to pasture B.

Output

Line 1: A single integer, the number of pastures that are reachable by all cows using the one-way paths.

Hint

In the example, the cows can meet in pasture 3 or pasture 4, so there are 2 possible picnic locations.

Examples3

Example 1
Input
```
2 4 4
2
3
1 2
1 4
2 3
3 4
```
Expected output
```
2
```
Example 2
Input
```
2 4 2
1
3
1 2
3 4
```
Expected output
```
0
```
Example 3
Input
```
3 5 3
1
2
3
1 5
2 5
3 5
```
Expected output
```
1
```