Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.
You are given a consists of nodes and edges.
A little bug is currently at node and wants to reach node with the shortest possible path.
He must visit nodes , , . . . . . . , , as the given sequence. For each , he can't visit node before visiting node .
He may visit as many nodes as he wants between nodes → , node → and so on.
You have to find the shortest possible path from node to 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.
The first line of input will consist of three integers and .
Each of the next lines will contain two integers and denoting there is a directed edge from node to node . There are no multiple edges.
The Next line will contain distinct space separated integers and .
There is only one line of output with two space separated integers and , denoting the length of the shortest possible path if there have any and total number of possible shortest path(s) Modulo .
It there is not any path fulfilling the requirements just print instead.
Input | Output |
---|---|
6 7 4 1 2 2 3 2 4 2 5 3 6 5 6 6 4 1 2 6 4 | 4 2 |
Input | Output |
---|---|
4 4 4 1 2 1 3 3 2 2 4 1 2 4 3 | -1 |
Input | Output |
---|---|
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 |
Login to submit
Firstly, let's reverse the direction of all the edges. Secondly, let's run BFSBFSBFS from each node ...