Problem Description

Birdstorm and hahaha are playing a game. Given a DAG (Directed acyclic graph) with n nodes and m edges. There are total k stones on the nodes and each node can contains more than one stone. Each turn, one can move at most two stones alone the edge, and he is lost if he can not move any one. Birdstorm move first and he wants to know how many ways to do his first operation that he can win the game.

Input

There are multiple test case. Each case begin with n(1<=n<=5000), m(1<=m<=100000), k(1<=k<=300). Next m lines, each lines contains two integers u, v, indicates an edge from u to v. Then a line with k numbers, indicates the position of the i-th stone.

Output

Each test case, print one line, the number of ways.

4 3 1
2 1
3 2
3 4
3

1

Author

BUPT