問題文

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

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

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

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

制約

• $3 \leq N \leq 10^5$
• $N-1 \leq M \leq 10^5$
• $1 \leq a_i < b_i \leq N$
• グラフは連結である。
• $1 \leq Q \leq 10^5$
• $1 \leq x_j < y_j \leq N$
• $3 \leq z_j \leq 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