Once again, James Bond is on his way to saving the world. Bond's latest mission requires him to travel between several pairs of cities in a certain country.

The country has N cities (numbered by 1, 2, . . ., N), connected by M bidirectional roads. Bond is going to steal a vehicle, and drive along the roads from city s to city t. The country's police will be patrolling the roads, looking for Bond, however, not all roads get the same degree of attention from the police.

More formally, for each road MI6 has estimated its dangerousness, the higher it is, the more likely Bond is going to be caught while driving on this road. Dangerousness of a path from s to t is defined as the maximum dangerousness of any road on this path.

Now, it's your job to help Bond succeed in saving the world by finding the least dangerous paths for his mission.

Input

There will be at most 5 cases in the input file.

The first line of each case contains two integers N, M (2 ≤ N≤ 50000, 1≤ M ≤ 100000) – number of cities and roads. The next M lines describe the roads. The i-th of these lines contains three integers: x_i, y_i, d_i (1 ≤ x_i, y_i ≤ N, 0 ≤ d_i ≤ 10⁹) - the numbers of the cities connected by the ith road and its dangerousness.

Description of the roads is followed by a line containing an integer Q (1 ≤ Q ≤ 50000), followed by Q lines, the i-th of which contains two integers s_i and t_i (1 ≤ s_i, t_i  ≤ N, s_i != t_i).

Consecutive input sets are separated by a blank line.

Output

For each case, output Q lines, the i-th of which contains the minimum dangerousness of a path between cities s_i and t_i. Consecutive output blocks are separated by a blank line.

The input file will be such that there will always be at least one valid path.

ProblemSetter: Ivan Krasilnikov

題目描述：

邦德(Bond) 要從某一個城市移動到另一個城市，每個路徑上都有危險度，為了怕被警察抓到，
邦德盡可能走危險度最低的路徑，也就是說他會走一條路徑上最大危險度中最小的那一條。

題目有多組詢問，輸出最小最大危險度路徑的值。

題目解法：

很明顯地，盡可能使用危險度低的建造一張圖，而所有簡單路徑在上面運行。
因此，我們需要使用最小生成樹，如此一來可以保證所有路徑只會發生在這棵樹上。

現在問題變成，找樹上的最大瓶頸路，先將樹轉換成有根樹。
思考一下 LCA 的問題(最鄰近共同祖先)，雖然問題差不多，但是為了求出最大瓶頸路到共同祖先，
我們考慮使用倍增算法，從這個節點開始，往上爬 1 層 2 層 4 層 8 層 ... 的最大瓶頸路，
這裡的遞迴條件是很簡單的。

對於如何查找就稍微困難些，首先，我們將每一個節點按照深度分層，對於查找 (x, y)，
事先將調整到相同層，再根據 greedy 的方式，將他們推到共同祖先。

建表 O (n log n)，每次查詢 O(log n)

#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
struct E {
    int x, y, v;
    E(int a=0, int b=0, int c=0):
        x(a), y(b), v(c) {}
    bool operator<(const E &a) const {
        return v < a.v;
    }
};
struct Edge {
    int to, v;
    Edge(int a=0, int b=0):
        to(a), v(b)  {}
};
E D[100005];
vector<Edge> g[50005];
int parent[50005], rank[50005];
int getParent(int x) {
    return parent[x] == x ? x : parent[x]=getParent(parent[x]);
}
int joint(int x, int y) {
    x = getParent(x), y = getParent(y);
    if(x == y)    return 0;
    if(rank[x] > rank[y])
        rank[x] += rank[y], parent[y] = x;
    else
        rank[y] += rank[x], parent[x] = y;
    return 1;
}
void MST(int n, int m) {//Kruskal algorithm
    sort(D, D+m);
    int i;
    for(i = 1; i <= n; i++) {
        g[i].clear();
        parent[i] = i, rank[i] = 1;
    }
    for(i = 0; i < m; i++) {
        if(joint(D[i].x, D[i].y)) {
            g[D[i].x].push_back(Edge(D[i].y, D[i].v));
            g[D[i].y].push_back(Edge(D[i].x, D[i].v));
        }
    }
}
int depth[50005], visited[50005];
int dp[50005][18], dpRoot[50005][18];// Doubling algorithm
void dfs(int nd, int p, int w) {
    visited[nd] = 1;
    depth[nd] = depth[p]+1;
    dpRoot[nd][0] = p;
    dp[nd][0] = w;
    int i, j;
    Edge e;
    for(i = 1, j = 2; j <= depth[nd]; i++, j <<= 1) {
        dp[nd][i] = max(dp[nd][i-1], dp[dpRoot[nd][i-1]][i-1]);
        dpRoot[nd][i] = dpRoot[dpRoot[nd][i-1]][i-1];
    }
    for(i = g[nd].size()-1; i >= 0; i--) {
        e = g[nd][i];
        if(e.to == p)    continue;
        dfs(e.to, nd, e.v);
    }
}
int query(int x, int y) {
    int ret = -0xfffffff;
    int i, j;
    if(depth[x] < depth[y])
        swap(x, y);
    if(depth[x] > depth[y]) {// adjust same level.
        int diff = depth[x] - depth[y];
        for(i = 0; diff; i++) {
            if((diff>>i)&1) {
                ret = max(ret, dp[x][i]);
                x = dpRoot[x][i];
                diff ^= 1<<i;
            }
        }
    }
    if(x != y) {
        for(i = 16; i >= 0; i--) {
            if(dpRoot[x][i] != dpRoot[y][i]) {
                ret = max(ret, dp[x][i]);
                ret = max(ret, dp[y][i]);
                x = dpRoot[x][i];
                y = dpRoot[y][i];
            }
        }
        ret = max(ret, dp[x][0]);
        ret = max(ret, dp[y][0]);
    }
    return ret;
}
int main() {
    int n, m, q;
    int i, j, x, y;
    int cases = 0;
    while(scanf("%d %d", &n, &m) == 2) {
        if(cases++)   
            puts("");
        for(i = 0; i < m; i++)
            scanf("%d %d %d", &D[i].x, &D[i].y, &D[i].v);
        MST(n, m);
        memset(visited, 0, sizeof(visited));
        memset(dp, 0, sizeof(dp));
        memset(dpRoot, 0, sizeof(dpRoot));
        depth[0] = 0;//init
        for(i = 1; i <= n; i++) {
            if(visited[i] == 0) {
                dfs(i, 0, 0);
            }
        }
        scanf("%d", &q);
        while(q--) {
            scanf("%d %d", &x, &y);
            printf("%d\n", query(x, y));
        }
    }
    return 0;
}
/*
4 5
1 2 10
1 3 20
1 4 100
2 4 30
3 4 10
2
1 4
4 1
 
2 1
1 2 100
1
1 2
*/