题目描述

有一张 $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$，表示一次询问。

输出格式

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

样例 1

输入

5 6
2 3
4 5
1 2
1 3
1 4
1 5
6
2 4 3
2 4 4
2 4 5
1 3 3
1 3 4
1 3 5

输出

1
2
3
1
5
5

说明/提示

由 yangyang1000 翻译

$1 \le n,m,Q \le 10^5$