# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# How Many Shortest Paths?

By Peregrine_Falcon · Limits 1s, 256 MB

You are given a $Directed$ $Acyclic$ $Graph$ consists of $N$ nodes and $M$ edges.

A little bug is currently at node $a_1$ and wants to reach node $a_x$ with the shortest possible path.
He must visit nodes $a_1$, $a_2$, . . . . . . , $a_x$, as the given sequence. For each $i$, he can't visit node $a_i$ before visiting node $a_{i-1}$.
He may visit as many nodes as he wants between nodes $a_1$$a_2$, node $a_2$$a_3$ and so on.

You have to find the shortest possible path from node $a_1$ to $a_x$ while fulfilling the requirements. You are also asked to find the total number of possible shortest path(s). Or report if it is impossible to find such a path.

## Input

The first line of input will consist of three integers $N,$ $M,$ and $X$ $(3 ≤ X ≤ N ≤ M ≤ 5 × 10^5)$.

Each of the next $M$ lines will contain two integers $U$ and $V$ $( 1 ≤ U, V ≤ N)$ denoting there is a directed edge from node $U$ to node $V$. There are no multiple edges.

The Next line will contain $X$ distinct space separated integers $a_i$ $( 1≤ i ≤ X$ and $1 ≤ a_i ≤ N)$.

## Output

There is only one line of output with two space separated integers $A$ and $B$, denoting the length of the shortest possible path if there have any and total number of possible shortest path(s) Modulo $100000110059$.
It there is not any path fulfilling the requirements just print $-1$ instead.

## Samples

InputOutput
6 7 4
1 2
2 3
2 4
2 5
3 6
5 6
6 4
1 2 6 4

4 2

InputOutput
4 4 4
1 2
1 3
3 2
2 4
1 2 4 3

-1

InputOutput
8 9 4
1 2
1 3
2 4
3 4
4 5
5 6
5 7
6 8
7 8
1 4 5 8

5 4


### Statistics

61% Solution Ratio

kzvd4729Earliest, 1M ago

RUDRA_DASFastest, 0.1s

PiasRoYLightest, 26 MB

serotoninShortest, 1166B