SP10704 MYQ12 - The Great Escape

A map consists of N checkpoints (numbered from 1 to N) connected by M one way roads. A thief is at checkpoint S. He wants to move to checkpoint D. The police, guessing that the thief will move through the route that takes him the least time to reach D from S, have called for security alerts to be placed in all the roads of all such routes. The thief wants to reach D without passing through any of those security alerted roads in the least possible time. If there are multiple such routes, he wants to travel so as to cross a minimum number of checkpoints. Find the minimum time required by the thief to reach D from S, the minimum number of checkpoints in such a route and the number of such routes available. Since the number of such routes may be huge, print the number of such routes modulo 1000000007. **Input** The first line of the input consists of a single integer t representing the number of test cases(1

N/A

For each test Case, output a single line containing 3 integers x,y,z. Where x is the least amount of time needed to travel from S to D without using any of the security alerted roads, y is the minimum number of checkpoints in such a route and z is the number of such routes modulo 1000000007. If there is no such path print -1.