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 DirectedDirected AcyclicAcyclic GraphGraph consists of NN nodes and MM edges.

A little bug is currently at node a1a_1 and wants to reach node axa_x with the shortest possible path.
He must visit nodes a1a_1, a2a_2, . . . . . . , axa_x, as the given sequence. For each ii, he can't visit node aia_i before visiting node ai1a_{i-1}.
He may visit as many nodes as he wants between nodes a1a_1a2a_2, node a2a_2a3a_3 and so on.

You have to find the shortest possible path from node a1a_1 to axa_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,N, M,M, and XX (3XNM5×105)(3 ≤ X ≤ N ≤ M ≤ 5 × 10^5).

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

The Next line will contain XX distinct space separated integers aia_i (1iX( 1≤ i ≤ X and 1aiN)1 ≤ a_i ≤ N).

Output

There is only one line of output with two space separated integers AA and BB, denoting the length of the shortest possible path if there have any and total number of possible shortest path(s) Modulo 100000110059100000110059.
It there is not any path fulfilling the requirements just print 1-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

    Discussion

    Statistics


    61% Solution Ratio

    kzvd4729Earliest, 1M ago

    RUDRA_DASFastest, 0.1s

    PiasRoYLightest, 26 MB

    serotoninShortest, 1166B

    Submit

    Login to submit

    Editorial

    Firstly, let's reverse the direction of all the edges. Secondly, let's run BFSBFSBFS from each node ...

    Related Contests