Kruskal's Ball

You are given an undirected graph. A special ball will be placed on one of its vertices.

The ball starts at a very low temperature, but its temperature keeps increasing over time. The ball can move across an edge only when its current temperature is at least the edge's unique value. In other words, at temperature t, it may use only edges whose values are at most t.

For each query, suppose the ball is placed on vertex x. Find the minimum temperature at which it can reach vertex y. Also find how many vertices the ball can reach at that minimum temperature.

The first line contains the number of vertices n and the number of edges m.

Each of the next m lines contains three integers a b c, meaning that the edge connecting vertices a and b has unique value c.

The next line contains the number of queries Q. Each of the following Q lines contains two integers x y.

The constraints are as follows.

• 1 <= n, m, Q <= 100,000
• 1 <= c <= 1,000,000
• x != y
• Vertices are numbered from 1 to n.
• No two edges have the same unique value.

Print one line for each query.

If the minimum temperature that lets the ball move from x to y is c, and the number of vertices reachable at that temperature is v, print c v.

If there is no path from x to y, print -1.