Little Horse 醒来发现自己身处一座荒岛上。离开荒岛的唯一方法是划船。

这里有 $n$ 座岛屿，编号从 $1$ 到 $n$。Little Horse 从其中一座岛屿出发，他需要到达第 $n$ 座岛屿以获救。共有 $m$ 条水道，每条水道连接两座岛屿。在每条水道中，水流从一座岛屿流向另一座。Little Horse 将按顺序执行以下步骤：

1. 划船。在这一步中，他最多可以通过 $k$ 条（可能为零）水道，无论是顺流还是逆流。通过每条水道需要花费 $1$ 个单位时间。
2. 休息。在这一步中，他将随机选择一条顺流的水道并随波漂流。除非当前岛屿没有可供漂流的顺流水道，否则他不能停留在当前岛屿。无论他是否移动，休息都需要花费 $1$ 个单位时间。
3. 回到第 1 步。

一旦 Little Horse 到达第 $n$ 座岛屿，他将立即停止。请告诉 Little Horse，如果他从第 $i$ 座岛屿出发，在最坏情况下他将花费的最少时间单位是多少。

输入格式

输入的第一行包含一个整数 $T$ ($1 \le T \le 10$) —— 测试用例的数量。

每个测试用例的第一行包含三个整数 $n, m, k$ ($1 \le n \le 10^5, 0 \le m \le 10^5, 0 \le k \le 50$) —— 岛屿和水道的数量，以及 Little Horse 划船时最多可以通过的水道数量。$n$ 的总和与 $m$ 的总和均不超过 $10^5$。

接下来的 $m$ 行，每行包含两个整数 $u, v$ ($1 \le u, v \le n, u \neq v$)，表示在岛屿 $u$ 和 $v$ 之间有一条水道，且水流从 $u$ 流向 $v$。保证 $m$ 条水道各不相同，但可能存在从 $u$ 到 $v$ 的水道，同时也存在从 $v$ 到 $u$ 的水道。

输出格式

第 $x$ 个测试用例的输出以 Case #x: 开头，占一行。

接下来的 $n$ 行中，第 $i$ 行包含一个整数，表示如果 Little Horse 从第 $i$ 座岛屿出发，在最坏情况下的最少时间单位。如果他在最坏情况下无法到达第 $n$ 座岛屿，则输出 $-1$。

样例

样例输入 1

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

样例输出 1

Case #1:
1
1
0
Case #2:
-1
1
0
Case #3:
5
2
1
0