問題文

$N$ 頂点 $M$ 辺の無向グラフがあります。 頂点は $1$ から $N$ まで番号が振られています。 辺は $1$ から $M$ まで番号が振られています。 辺 $i$ は頂点 $a_i$ と $b_i$ を結んでいます。 グラフは連結です。

このグラフの上で、$Q$ 組の兄弟がスタンプラリーをします。 $j$ 組目の兄弟は次のようなスタンプラリーをします。

• 最初、兄は頂点 $x_j$ に、弟は頂点 $y_j$ にいる。
• 兄弟でちょうど $z_j$ 個の頂点を訪れる。 ただし、同一の頂点を兄弟ともに訪れた場合でも、$2$ 個の頂点を訪れたとは見なさない。
• 兄または弟が通った辺の番号の最大値がスコアとなる。 兄弟はこのスコアをできるだけ小さくする。

それぞれの兄弟のスコアを求めてください。

制約

• $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$ 行出力せよ。 $j$ 行目には、$j$ 組目の兄弟のスコアを出力せよ。

入力例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