Home

Contest: Task: Related: TaskC TaskE

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

Sample Output 1