题目描述

我们有一个无向图，包含 $N$ 个顶点和 $M$ 条边。顶点编号从 $1$ 到 $N$，边的编号从 $1$ 到 $M$。边 $i$ 连接了顶点 $a_i$ 和 $b_i$。图是连通的。

在这个图上，有 $Q$ 对兄弟参加了一项名为“集邮活动”的活动。第 $i$ 对兄弟的集邮活动规则如下：

• 兄弟中的一个从顶点 $x_i$ 开始，另一个从顶点 $y_i$ 开始。
• 两个兄弟沿着边探索图，总共访问 $z_i$ 个顶点，包括起始顶点。在此过程中，即使同一个顶点被多次访问或者被两个兄弟同时访问，也只计数一次访问。
• 分数定义为两个兄弟所经过的边中最大的边的索引号。他们的目标是最小化这个值。

找到每对兄弟的最小可能分数。

约束条件

• $3≤N≤10^5$
• $N−1≤M≤10^5$
• $1≤a_i<b_i≤N$
• 给定的图是连通的。
• $1≤Q≤10^5$
• $1≤x_j<y_j≤N$
• $3≤z_j≤N$

输入

输入以以下格式从标准输入中给出：

$N$ $M$ $a_1$ $b_1$ $a_2$ $b_2$ $:$ $a_M$ $b_M$ $Q$ $x_1$ $y_1$ $z_1$ $x_2$ $y_2$ $z_2$ $:$ $x_Q$ $y_Q$ $z_Q$

输出

输出 $Q$ 行，第 $i$ 行应包含第 $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

1
2
3
1
5
5