Problem E
Pachinko Probability

Image from Wikipedia.

A pachinko machine is a Japanese invention that is sort of like a pinball machine. Each pachinko machine uses marbles which fall from the top and bounce off of fixed pins until they reach the bottom. When they reach the bottom, if they fall into a particular area (a ‘gate’), then that round wins; otherwise, the round loses.

Figure 1: Sample data illustrations. The rectangular nodes are gates.

In Figure 1, which illustrates the sample inputs, the nodes represent possible marble locations (nodes are not the pins; they are between the pins), the boxes represent gates, and the edges represent possible transitions between locations. Write a program to find out how likely it is that you can win at pachinko.

Input

Input contains a description of a single machine, which is given as a directed acyclic graph indicating the places a marble can travel as it proceeds from the top to the bottom. A marble may start at any graph node that has no incoming edges, and always ends at a node having no outgoing edges. Each machine starts with a line containing an integer $1 \leq n \leq 1\, 000$, indicating the number of nodes in the graph (nodes are numbered $0$ to $n-1$). The next line contains an integer $0 \leq m \leq \min (n(n-1)/2,10\, 000)$ indicating the number of edges in the graph. The following $m$ lines each contain two integers $x$ and $y$ (both in the range $[0,n-1]$), indicating that node $x$ leads to node $y$. Finally, the last line of a machine’s description has an integer $0 \leq k \leq n$ indicating how many gates there are. This is followed by $k$ numbers in the range $[0,n-1]$ indicating the gates, one per line. Every gate is a node with no outgoing edges.

Output

Print out the number of possible winning paths (those ending in a gate) and the total number of possible paths. Do not reduce these numbers. A ‘possible path’ is any sequence of graph nodes that lead from a starting node to an ending node.

3
2
0 1
0 2
1
1

winning paths 1
total paths 2

6
8
0 2
0 3
1 2
1 3
2 4
2 5
3 4
3 5
1
4

winning paths 4
total paths 8