AT_agc002_d [AGC002D] Stamp Rally

有一张 $n$ 个点，$m$ 条边的无向图，点的编号从 $1$ 到 $n$，边的编号从 $1$ 到 $m$，第 $i$ 条边连接定点 $a_i$ 和 $b_i$。**保证图联通**。 在这张图上，有 $Q$ 次询问，每次询问中有一对兄弟进行如下操作： - 最开始的时候哥哥在 $x_i$ 点，弟弟在 $y_i$ 点，兄弟两人可以通过边从一个点走到另一个点。 - 兄弟俩需要总计访问恰好 $z_i$ 个顶点。不过哥哥弟弟都访问的顶点只能算一个。 - 其中兄弟俩经过的边的编号最大值为代价。兄弟俩希望最小化代价。 求每组兄弟的代价。

第一行包含两个正整数 $N$ 和 $M$。 接下来 $M$ 行，每行包含两个正整数 $a_i, b_i$，表示 $a_i$ 和 $b_i$ 之间有一条无向边。 接下来一行包含一个正整数 $Q$。 接下来 $Q$ 行，每行包含三个整数 $x_i, y_i, z_i$，表示一次询问。

对于每个询问，输出一行一个整数，表示答案。

由 [yangyang1000](https://www.luogu.com.cn/user/636442) 翻译