该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

伞伞骑着他 $25$ 手的单车在城市之中自由穿梭！

城市中共有 $n$ 个地点，这些地点之间存在 $m$ 条 双向 道路。两个地点间可能有多条道路，且不保证任意两个地点都可以通过道路相互到达，但保证同一个地点不会连出一条道路到自己。

每条道路都有一个粗糙程度值 $w$，这个值越高代表这条道路越难行走。每条道路都可以多次通过。

如果伞伞进入这条道路时的速度为 $v$，那么伞伞驶出这条道路时的速度会变为 $\lfloor \frac{v}{w} \rfloor$。

伞伞此时到达了地点 $c$，并且把车速提升到了 $x$。突然，他发现他新买的单车刹车坏了！他只能硬着头皮继续骑，直到单车停下来。

伞伞车技高超，可以瞬间将车头调整到任意方向。他想知道，最少还要再经过多少条道路，才能使单车的速度降为 $0$！关键时刻，请你帮帮他！

输入格式

从文件 free.in 读入数据。 第一行三个正整数 $n,m,q$，表示地点数量、道路数量、询问次数。

接下来 $m$ 行，每行三个正整数 $u_i,v_i,w_i$，表示一条连接 $u_i$ 和 $v_i$ 的双向道路，粗糙程度为 $w_i$。

接下来 $q$ 行，每行两个正整数 $c_i,x_i$，表示伞伞此时的位置和车速。

建议使用较快的读入方式。

输出格式

输出到文件 free.out。 如果伞伞可以停下来，输出一个非负整数 $s$ 表示最少需要经过的道路数，否则输出 Good luck! 表示祝伞伞好 （chong） 运 （kai）。

4 2 5
1 2 2
2 3 3
1 5
1 7
2 2
3 0
4 1

2
3
1
0
Good luck!

6 7 6
1 2 1
2 3 2
3 4 7
4 5 1
5 6 4
6 1 2
2 5 3
1 10
2 100
3 0
4 50
5 100
6 20

3
4
0
3
4
3

解释

第一组数据中，地点 $4$ 没有连出任何道路，速度永远不会变化，输出 Good luck!。从地点 $1$ 出发且速度为 $7$ 时，沿着 $1 \to 2 \to 3 \to 2$ 骑行，速度依次变为 $3,1,0$，共经过 $3$ 条道路。

第二组数据中，从地点 $4$ 出发且速度为 $50$ 时，沿着 $4 \to 3 \to 4 \to 3$ 骑行，速度依次变为 $7,1,0$，共 $3$ 条道路；从地点 $5$ 出发且速度为 $100$ 时，沿着 $5 \to 6 \to 5 \to 6 \to 5$ 骑行，速度依次变为 $25,6,1,0$，共 $4$ 条道路。

样例 3

见 free3.in 与 free3.ans。

样例 4

见 free4.in 与 free4.ans。

样例 5

见 free5.in 与 free5.ans。

样例 6

见 free6.in 与 free6.ans。

样例 7

见 free7.in 与 free7.ans。

数据规模与约定

下发文件分别对应子任务 $1,2,3,4,5$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1 \leq n,m \leq 2 \times 10^5,1 \leq q \leq 10^6, 1 \leq u_i,v_i,c_i \leq n,u_i \neq v_i,1 \leq w_i \leq 10^9,0 \leq x_i \leq 10^9$。

时空限制：$4$ 秒 / $512\,\mathrm{MiB}$。