The programming club at Don Mills has been booming lately, and so Griffy has decided to install a system to figure out the path that students should take to reach the club room (which is not necessarily held in the same room every time). He hopes that this act of kindness will weaken Timothy Li's defenses so he will be able to beat him up at tic-tac-toe. There are ~N~ rooms numbered from ~1~ to ~N~, and ~M~ one-way hallways that connect two locations. Each hallway takes ~T~ minutes to traverse. Given ~Q~ queries in the form
a b, where ~a~ is not equal to ~b~, find the least amount of time needed to go from room ~a~ to room ~b~. If it is not possible to get from ~a~ to ~b~, output
Not enough hallways!.
First line, three integers ~N~ ~(2 \le N \le 1\,000)~, ~M~ ~(0 \le M \le 1\,000)~, ~T~ ~(1 \le T \le 1\,000)~.
Next ~M~ lines, two integers
a b on each line describing a one-way hallway from ~a~ to ~b~.
Line ~M+2~, one integer ~Q~ ~(1 \le Q \le 200\,000)~.
Lines ~M+3 \dots M+2+Q~, two integers
a b the query rooms.
One line for each query, the shortest amount of time taken to go from room ~a~ to room ~b~.
7 6 8 2 3 5 7 1 7 3 4 4 3 1 2 3 1 7 4 2 1 4
8 Not enough hallways! 24