题目描述

输入格式

第一行两个正整数，代表 $N$ 和 $M$。

接下来 $M$ 行，第 $i$ 行有两个正整数 $a_i,b_i$，代表 $a_i$ 和 $b_i$ 之间有一条无向边。

接下来一行有一个正整数，代表 $Q$。

接下来 $Q$ 行，第 $i$ 行有三个整数 $x_i,y_i,z_i$，表示一种询问。

输出格式

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

题目大意

一张连通图，$q$ 次询问从两个点 $x$ 和 $y$ 出发，希望经过的点数量等于 $z$（每个点可以重复经过，但是重复经过只计算一次），求经过的边最大编号最小是多少。

对于 $100\%$ 的数据，$3 \le N \le 10^5$，$N-1 \le 10^5$，$1 \le Q \le 10^5$，其它数据保证合法。

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