题目描述

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

城市中共有 $n$ 个地点，这些地点之间通过若干条有向道路相互连接。两个地点间可能有多条道路。

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

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

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

他想知道，最少还要经过多少条道路，才能使单车的速度降为 $0$！关键时刻，请你帮帮他！

输入格式

第一行三个正整数 $n,m,q$，表示地点数量、道路数量、询问次数。

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

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

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

输出格式

如果江桥可以停下来，输出一个非负整数 $s$ 表示最少需要经过的道路数，否则输出 Good luck! 表示祝江桥好运。

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

2
Good luck!
1
0

数据规模与约定

下发文件

下发文件对应子任务 $6$。

有合理的子任务依赖。

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