Expert.
Put your skills to the test.

Problem summary

For each lake pair, find the largest boat width that can travel along some route of undirected channels. A route is limited by its narrowest channel.

Source clarification. The statement describes routes between two lakes and does not define a finite capacity for a zero-length route from a lake to itself. The implementation follows the intended distinct-endpoint queries; the source does not explicitly spell out this convention.

Constraints

N≤1000;M≤100000;K≤10000;channel widths≤200;queried pairs are connected.

Worked example

An independently prepared worked example; constructive outputs may have other valid forms.

6 9 4
1 2 2
1 4 3
1 6 1
2 3 3
2 5 2
3 4 4
3 6 2
4 5 5
5 6 4
2 6
3 5
1 2
4 6

3
4
3
4

Solution analysis

1. Sort channels by decreasing width and run Kruskal’s algorithm. The selected edges form a maximum spanning forest; retain them as an adjacency list.
2. For a query, traverse the unique forest path from its first lake. Carry the minimum edge width seen so far. That minimum at the destination is the answer. N≤1000 allows an O(N) traversal per query without LCA machinery.
3. In the sample, a route2→3→4→5→6 has minimum width min(3,4,5,4)=3. No route can support a wider boat, so the first answer is3.

Why it works

For any threshold w, Kruskal’s forest connects exactly the vertices connected by original channels of width at least w: all such edges are processed before smaller ones. The largest threshold connecting a query pair therefore equals the minimum width on its forest path.

Watch out. Use a maximum, not minimum, spanning forest. Along a route take the minimum edge, then maximize over routes. The source does not define an unrestricted zero-length journey; distinct endpoints are the natural query interpretation.

An independently written complete program with standard headers.

// Key idea: For any threshold w, Kruskal’s forest connects exactly the vertices connected by original
// channels of width at least w: all such edges are processed before smaller ones. The largest
// threshold connecting a query pair therefore equals the minimum width on its forest path.
#include<algorithm>
#include<iostream>
#include<numeric>
#include<tuple>
#include<utility>
#include<vector>
using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,queries;
    cin>>n>>m>>queries;
    vector<tuple<int,int,int>>edges;
    for(int i=0;i<m;i++){
        int a,b,width;
        cin>>a>>b>>width;
        edges.push_back({width,a,b});
    }
    sort(edges.rbegin(),edges.rend());
    vector<int>parent(n+1),size(n+1,1);
    iota(parent.begin(),parent.end(),0);
    auto find=[&](int vertex){
        int root=vertex;
        while(parent[root]!=root){
            root=parent[root];
        }
        while(parent[vertex]!=vertex){
            int next=parent[vertex];
            parent[vertex]=root;
            vertex=next;
        }
        return root;
    };
    vector<vector<pair<int,int>>>forest(n+1);
    for(auto[width,a,b]:edges){
        int x=find(a);
        int y=find(b);
        if(x==y){
            continue;
        }
        if(size[x]<size[y]){
            swap(x,y);
        }
        parent[y]=x;
        size[x]+=size[y];
        forest[a].push_back({b,width});
        forest[b].push_back({a,width});
    }
    while(queries--){
        int source,target;
        cin>>source>>target;
        vector<int>capacity(n+1,-1);
        vector<int>stack{source};
        capacity[source]=201;
        while(!stack.empty()){
            int v=stack.back();
            stack.pop_back();
            for(auto[to,width]:forest[v]){
                if(capacity[to]==-1){
                    capacity[to]=min(capacity[v],width);
                    stack.push_back(to);
                }
            }
        }
        cout<<capacity[target]<<'\n';
    }
}