Robots in a DAG

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
The annual Robotics Fest has started, and you have registered for an event in it, for which you have to build K robots and make them traverse a maze. The maze is in the form of a directed acyclic graph (DAG). That is, you can think that there is a graph with N vertices and M edges. Let the nodes be numbered from 1 to N. The edges are E_{1}, E_{2}, ..., E_{M}, where E_{i} = (u_{i}, v_{i}), denoting that a robot can travel from u_{i} to v_{i}.The robots start from node 1 and have to reach node N. The graph's edges do not form any directed cycles, and there are no selfloops or multiple edges.
All the K robots travel at the speed of 1 edge per second, and all of them start at the same time. Once a robot reaches node N, it is taken out of the maze. But till then, a robot has to keep moving. That is, a robot cannot wait at any node. And since the maze's paths are narrow, at most one robot can traverse that edge in any given second.
Formally, we can represent the ith robot's trip using a series of edges: E_{i1}, E_{i2}, .., E_{ix}, where E_{i1} is an edge which goes out of node 1 and E_{ix} is an edge which goes into node N. For any i, j such that i ≠ j, there should not be a t, such that E_{it} = E_{jt}.
The aim of the contest is to program your robots in such a manner that they travel obeying these constraints, and minimizing the maximum distance traveled by your robots. That is, consider the number of edges traveled by a robot, and take the maximum of this among all your K robots. This value should be minimized. Output this minimum value. And if it is not possible to program the robots according to the conditions, output 1 instead.
Input
 The first line contains a single integer, T, denoting the number of testcases. The description of each testcase follows.
 The first line of each testcase contains three integers: N, M and K, denoting the number of nodes, number of edges, and the number of robots respectively.
 The ith of the next M lines contains two integers, u_{i} and v_{i}, denoting that there is an edge from u_{i} to v_{i}.
Output
 For each testcase, output a single line containing a single integer which should be the minimum maximum distance traveled by the robots, or 1, if it is not possible to send all the K robots.
Constraints
 1 ≤ T ≤ 5
 2 ≤ N ≤ 100
 1 ≤ M, K ≤ 1000
 1 ≤ u_{i}, v_{i} ≤ N
Example
Input: 3 8 11 1 1 2 1 3 1 4 6 7 2 5 3 6 3 2 4 6 5 7 7 8 2 7 8 11 2 1 2 1 3 1 4 6 7 2 5 3 6 3 2 4 6 5 7 7 8 2 7 8 11 3 1 2 1 3 1 4 6 7 2 5 3 6 3 2 4 6 5 7 7 8 2 7 Output: 3 4 5
Explanation
The graphs in all the three testcases are the same. Only the number of robots change.
Test Case 1: There is only one robot, and it can take this sequence of edges: (1, 2), (2, 7), (7, 8). The maximum distance traveled among all the robot(s) is 3, and hence the answer is 3. This cannot be lowered.
Test Case 2: There are two robots, and one optimal solution is to make the first robot take this path: (1, 2), (2, 7), (7, 8) and make the second robot take this path: (1, 3), (3, 6), (6, 7), (7, 8). Note that the edge (7, 8) was traversed by both robots, but one did it at the third second, and the other at the fourth second, and hence it is allowed. The distances traveled by the robots are 3 and 4, and the maximum among that is 4. This cannot be lowered, and hence the answer is 4.
Test Case 3: There are three robots, and one optimal solution is to make the first robot take this path: (1, 2), (2, 7), (7, 8), make the second robot take this path: (1, 4), (4, 6), (6, 7), (7, 8) and make the third robot take this path: (1, 3), (3, 2), (2, 5), (5, 7), (7, 8). Note that the edge (7, 8) was traversed by all three robots, but one did it at the third second, one did it at the fourth second, and the other at the fifth second, and hence it is allowed. The distances traveled by the robots are 3, 4, and 5, and the maximum among them is 5. This cannot be lowered, and hence the answer is 5.
Author:  admin3 
Tags  admin3 
Date Added:  2062017 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 