Kruskal's Ball

Time limit2sMemory limit128 MB

Summary
Given a graph with unique edge weights, build a Kruskal reconstruction tree to answer queries about the minimum temperature needed to connect two vertices and the size of the reachable component at that temperature.
Level

Hard8 of 10

Topics
Minimum spanning tree, Union-find, Tree, Sorting
Solved
No attempts yet

Problem

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.

Input

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.

Output

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.

Examples1

  1. Example 1

    Input
    5 4
1 2 1
2 3 2
3 4 4
4 5 3
2
1 5
2 3
    Expected output
    4 5
2 3