크루스칼의 공

무방향 그래프가 주어진다. 그래프 위에 특별한 공을 하나 올려놓으려고 한다.

이 공의 온도는 처음에는 매우 낮지만, 시간이 지날수록 계속 올라간다. 공은 현재 온도가 어떤 간선의 고유값 이상일 때에만 그 간선을 지나 다른 정점으로 이동할 수 있다. 즉, 온도가 t라면 고유값이 t 이하인 간선만 이용할 수 있다.

각 쿼리마다 정점 x에 공을 놓았을 때 정점 y에 도달할 수 있게 되는 최소 온도를 구하라. 또한 그 최소 온도에서 공이 이동할 수 있는 정점들의 개수도 함께 구하라.

첫째 줄에 정점의 개수 n과 간선의 개수 m이 주어진다.

다음 m개 줄에는 세 정수 a b c가 주어진다. 이는 정점 a와 정점 b를 잇는 간선의 고유값이 c라는 뜻이다.

그다음 줄에 쿼리의 개수 Q가 주어진다. 이어지는 Q개 줄에는 두 정수 x y가 주어진다.

제한은 다음과 같다.

• 1 <= n, m, Q <= 100,000
• 1 <= c <= 1,000,000
• x != y
• 정점 번호는 1부터 n까지이다.
• 서로 다른 두 간선의 고유값은 같지 않다.

각 쿼리마다 한 줄에 답을 출력한다.

정점 x에서 출발한 공이 정점 y에 도달할 수 있게 되는 최소 온도를 c, 그 온도에서 공이 이동할 수 있는 정점의 개수를 v라고 할 때 c v를 출력한다.

만약 x에서 y로 갈 수 있는 경로가 아예 없다면 -1을 출력한다.