D - Stamp Rally Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

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

Problem Statement

We have an undirected graph with N vertices and M edges. The vertices are numbered 1 through N, and the edges are numbered 1 through M. Edge i connects vertices a_i and b_i. The graph is connected.

On this graph, Q pairs of brothers are participating in an activity called Stamp Rally. The Stamp Rally for the i-th pair will be as follows:

  • One brother starts from vertex x_i, and the other starts from vertex y_i.
  • The two explore the graph along the edges to visit z_i vertices in total, including the starting vertices. Here, a vertex is counted only once, even if it is visited multiple times, or visited by both brothers.
  • The score is defined as the largest index of the edges traversed by either of them. Their objective is to minimize this value.

Find the minimum possible score for each pair.

Constraints

  • 3≤N≤10^5
  • N−1≤M≤10^5
  • 1≤a_i<b_i≤N
  • The given graph is connected.
  • 1≤Q≤10^5
  • 1≤x_j<y_j≤N
  • 3≤z_j≤N

Input

The input is given from Standard Input in the following format:

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

Output

Print Q lines. The i-th line should contain the minimum possible score for the i-th pair of brothers.

Sample Input 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

Sample Output 1

1
2
3
1
5
5