Problem D
Panda Chess

Photo by brandiibear from Pinterest

In the city of Pandaville, the predominant black and white colours of the inhabitants have somehow made chess a very popular game in the area. There are a total of $N$ chess players in the city and they are very competitive. Recently, the annual Panda Chess Tournament has just ended where a total of $M$ matches have been played among the players to decide who is the best chess player. This has resulted in a unique ranking among the players such that for every match, the winner has a higher rank than the loser. The ranking will be published on The Daily Chess tomorrow.

Each chess player is identified by his/her unique IC number which is a number containing at most $D$ digits from $0$ to $9$. The ranking is a list of IC numbers ordered by their relative ranks with the top player being the first in the list.

The ranking list published is typed by a panda writer using a typewriter. Due to his fat paws, the panda writer makes a lot of mistakes. You are asked to amend the ranking list. $1$ edit is defined as either removing an IC number or inserting an IC number into the list. You aim to find out what is the least number of edits required to correct the ranking list.

Input

The input consists of:

• One line with three integers $N$ ($2 \le N \le 100\, 000$), $M$ ($1 \le M \le 200\, 000$) and $D$ ($1 \le D \le 10$), where $N$ is the number of chess players, $M$ is the number of matches played, and $D$ is the maximum number of digits for each IC number;

• $M$ lines each with two IC numbers $A$ and $B$, indicating that panda A wins over panda B;

• $N$ lines each with one IC number $C$, representing the ranking list typed by the panda writer;

It is guaranteed that the $M$ matches define one unique ranking for the $N$ pandas and every match will be played between $2$ different players. However, $2$ players can play more than once.

Output

Output one line with a single integer: the minimum number of edits required to obtain the actual ranking list from the original ranking list typed by the panda writer.

4 4 3
345 678
12 345
345 678
678 999
999
12
824
999

4