Description

$\text{sideman}$ has prepared the hardware to return to the planet $\text{Gliese}$, but $\text{sideman}$'s navigation system is not fully designed yet. For convenience, we can regard the universe as a weighted undirected graph with $N$ vertices and $M$ edges. Vertices represent galaxies, an edge between two galaxies means there is a direct flight between them, and the edge weight is the danger level of the voyage.

Now $\text{sideman}$ wants to minimize the danger level. Specifically, for several queries $(A, B)$, $\text{sideman}$ wants to know the minimal possible value of the danger level of the most dangerous edge along a route from vertex $A$ to vertex $B$. As $\text{sideman}$'s classmates, you should help $\text{sideman}$ return home and enjoy a safe and beautiful journey through the universe. So this task is yours.

Input Format

The first line contains two positive integers $N$ and $M$, the number of vertices and edges.

Each of the next $M$ lines contains three integers $A$, $B$, and $L$, indicating that there is an edge of length $L$ between vertices $A$ and $B$. Vertices are numbered starting from $1$.

The next line contains a positive integer $Q$, the number of queries.

Each of the next $Q$ lines contains two integers $A$ and $B$, asking for the minimal possible value of the danger level of the most dangerous edge along any path between $A$ and $B$.

Output Format

For each query, output the result on a separate line. If the two vertices are not reachable from each other, output $\text{impossible}$.

4 5
1 2 5
1 3 2
2 3 11
2 4 6
3 4 4
3
2 3
1 4
1 2

5
4
5

Hint

For $40\%$ of the testdata, $N \leq 1000$, $M \leq 3000$, $Q \leq 1000$.

For $80\%$ of the testdata, $N \leq 10000$, $M \leq 10^5$, $Q \leq 1000$.

For $100\%$ of the testdata, $N \leq 10^5$, $M \leq 3 \times 10^5$, $Q \leq 10^5$, $L \leq 10^9$. The testdata do not guarantee the absence of parallel edges and self-loops.

Translated by ChatGPT 5