E. Escape from the Island
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Little Horse wakes up and finds himself located on a desert island. The only way to escape from the island is by rowing a boat.

There are $$$n$$$ islands numbered from $$$1$$$ to $$$n$$$. Little Horse starts from one of these islands, and he needs to reach the $$$n$$$-th island to be rescued. There are $$$m$$$ waterways, each of which connects two islands. In each waterway, the water flows from one island to the other one. Little Horse will apply the following steps in order:

  1. Row the boat. At this step, he can go through at most $$$k$$$ (possibly zero) waterways, either downstream or upstream. Going through each waterway will take $$$1$$$ time unit.
  2. Take a rest. At this step, he will randomly choose a waterway downstream and drift through it. He cannot stay at the current island unless there is no such waterway to drift through. Whether he moves or not, taking a rest will take $$$1$$$ time unit.
  3. Go back to step 1.

Once Little Horse reaches the $$$n$$$-th island, he will stop immediately. Please tell Little Horse that if he starts from the $$$i$$$-th island, what's the minimum time units he will spend in the worst case.

Input

The first line of the input contains an integer $$$T$$$ ($$$1 \le T \le 10$$$) — the number of test cases.

The first line of each test case contains three integers $$$n,m,k$$$ ($$$1 \le n\le 10^5$$$, $$$0 \le m \le 10^5$$$, $$$0 \le k \le 50$$$) — The number of islands and waterways, and the maximum number of waterways Little Horse can go through when he rows the boat. The sum of $$$n$$$ and the sum of $$$m$$$ will not exceed $$$10^5$$$.

Then in the next $$$m$$$ lines, each line contains two integers $$$u,v$$$ ($$$1 \le u,v \le n$$$, $$$u \neq v$$$), which means there's a waterway between island $$$u$$$ and $$$v$$$, and the water flows from $$$u$$$ to $$$v$$$. It's guaranteed that the $$$m$$$ waterways are all distinct, but it's possible that there's a waterway from $$$u$$$ to $$$v$$$ and also a waterway from $$$v$$$ to $$$u$$$.

Output

The output of the $$$x$$$-th case begins with $$$Case$$$ #$$$x$$$: in a single line.

Then in the next $$$n$$$ lines, the $$$i$$$-th line contains an integer indicating the minimum time units in the worst case if Little Horse starts from the $$$i$$$-th island. If he cannot reach the $$$n$$$-th island in the worst case, output $$$-1$$$.

Example
Input
3
3 3 1
1 2
2 3
1 3
3 2 1
2 1
3 2
4 3 2
2 1
3 2
4 3
Output
Case #1:
1
1
0
Case #2:
-1
1
0
Case #3:
5
2
1
0