Dog Trick Competition

Task

RANDy is back at it again, but now he is ready to showcase his elite dog training skills. He's been training his dog Pompieru for many years, and now he is ready to participate in a dog trick competition.

There are $K + 1$ tricks which can be performed in this competition, numbered from $1$ to $K + 1$.
Pompieru does not know how to perform the trick $K+1$, so he can only perform the tricks from $1$ to $K$.
Moreover, performing specific tricks one after the other is not always possible: he can only perform trick $b$ right after trick $a$ if he has been trained to do so.
RANDy trained Pompieru to perform $M$ pairs of consecutive tricks $(A_i, B_i)$, meaning that Pompieru knows how to perform trick $B_i$ right after trick $A_i$.

The participants are required to perform $N$ tricks $T_0, T_1, \ldots, T_{N-1}$ in this specific order.
For each successfully performed trick the dog gets $1$ point.
A dog may decide to skip a trick and continue with the next trick instead.
The dogs are allowed to skip any number of tricks, even if they know how to do the tricks, but if a dog skips two consecutive tricks it gets disqualified, scoring zero points.

Help RANDy and Pompieru find the maximum number of points $P$ they can score in this competition.

Input data

The input file consists of:

• a line containing integers $N$ and $K$.
• a line containing the $N$ integers $T_{0}, \, \ldots, \, T_{N-1}$.
• a line containing integer $M$.
• $M$ lines, the $i$-th of which consisting of integers $A_{i}$, $B_{i}$.

Output data

The output file must contain a single line consisting of integer $P$.

Constraints and clarifications

• $2 \le N \le 2 \cdot 10^5$.
• $1 \le K \le 2 \cdot 10^5$.
• $1 \le M \le 2 \cdot 10^5$.
• $1 \le T_i \le K + 1$ for each $i = 0 \ldots N - 1$.
• $1 \le A_i, B_i \le K$ for each $i = 0 \ldots M - 1$.
• All the pairs $(A_i, B_i)$ are distinct.

Example 1

stdin

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

stdout

4

Explanation

In the first sample case, Pompieru can skip the first trick, perform the second trick, skip the third and then perform the last three tricks, scoring $4$ points total.

Example 2

stdin

4 3
1 4 2 3
1
1 3

stdout

0

Explanation

In the second sample case, Pompieru can perform the first trick but does not know how to perform the second trick, so he has to skip it.
He can perform the third trick, but was not trained to perform it after the first trick, so he has to skip it again. Since he skipped two tricks in a row, he gets disqualified and scores $0$ points.