Untitled

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
int MAX[100001][20];
int MIN[100001][20];
int parent[100001][20];
int depth[100001];

bool vis[100001];

vector<pair<int,int>> G[100001];

void init_lca(){
    for(int i = 1;i<=19;i++){
        for(int j = 1;j<=100000;j++){
            parent[j][i] = parent[parent[j][i-1]][i-1]; 
            MAX[j][i] = max(MAX[j][i],MAX[parent[j][i-1]][i-1]);
            MIN[j][i] = min(MIN[j][i],MIN[parent[j][i-1]][i-1]);
        }
    }
}

void dfs(int cur, int d=0, int prev=0){
    vis[cur] = true;
    depth[cur] = d;
    for(pair<int,int> nxt : G[cur]){
        int nxt_node = nxt.first;
        int nxt_weight = nxt.second;
        if(!vis[nxt_node]){
            parent[nxt_node][0] = cur;
            MAX[nxt_node][0] = nxt_weight;
            MIN[nxt_node][0] = nxt_weight;
            dfs(nxt_node,d+1, cur);
        }
    }
}

int lca(int u, int v){

    if(depth[u] < depth[v]) swap(u,v);

    // int u_value = MAX[u][0];
    // int v_value = MIN[v][0];
    // cout << v_value << '\n';
    int diff = depth[u] - depth[v];
    for(int i=19;i>=0;i--){
        if(diff >=(1<<i)){
            diff-=(1<<i);
            u = parent[u][i];
            // u_value = max(u_value, MAX[u][i]);
            // v_value = min(v_value, MIN[v][i]);
        }
    }

    if(u==v) {
        // cout << u_value << " " << v_value << '\n';
        return u;
    }

    for(int i = 19;i>=0;i--){
        if(parent[u][i]!=parent[v][i]){
            u = parent[u][i];
            // u_value = max(u_value, MAX[u][i]);
            v = parent[v][i];
            // v_value = min(v_value, MIN[v][i]);
        }
    }
    // cout << u_value << " " << v_value << '\n';
    return parent[u][0];
}

void init(){
    cin >> n;
    int a, b, c;
    for(int i = 0;i<n-1;i++){
        cin >> a >> b >> c;
        G[a].push_back({b,c});
        G[b].push_back({a,c});
    }
    for(int i = 0;i<=100000;i++){
        for(int j = 0;j<=19;j++){
            MIN[i][j] = INT32_MAX;
            MAX[i][j] = -1;
        }
    }
}

pair<int, int> result_query(int u, int v){
    int LCA = lca(u,v);
    cout << LCA << '\n';
    // // u >> LCA 
    pair<int, int> M_m_u = {MAX[u][0], MIN[u][0]};
    int diff = depth[u] - depth[LCA];
    for(int i = 19;i>=0;i--){
        if(diff>=(1<<i)){
            M_m_u.first = max(M_m_u.first, MAX[u][i]);
            M_m_u.second = min(M_m_u.second, MIN[u][i]);
            u = parent[u][i];
        }
    }
    
    
    pair<int, int> M_m_v = {MAX[v][0], MIN[v][0]};
    
    diff = depth[v] - depth[LCA];
    for(int i = 19;i>=0;i--){
        if(diff>=(1<<i)){
            M_m_v.first = max(M_m_v.first, MAX[v][i]);
            M_m_v.second = min(M_m_v.second, MIN[v][i]);
            v = parent[v][i];
        }
    }
    if(u==LCA){
        return {min(M_m_v.first,M_m_v.second), max(M_m_v.first, M_m_v.second)};
    }
    if(v==LCA){
        return {min(M_m_u.first,M_m_u.second), max(M_m_u.first, M_m_u.second)};
    }
    return {min(M_m_v.second, M_m_u.second), max(M_m_v.first, M_m_u.first)};
}

void query(){
    int m;
    cin >> m;
    int D, E;
    
    while(m--){
        cin >> D >> E;
        // O(4log(N) * m)
        // cout << min(D,E) << " " << max(D,E) << '\n';
        // lca(D,E);
        pair<int,int> res = result_query(D,E);
        cout << res.first << " " << res.second << '\n';
    }

}

int main(void){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    init();
    dfs(1,0,0);
    init_lca();
    query();   
    // for(int i = 0;i<19;i++){
    //     cout << MIN[2][i] << " ";
    // }
    // cout << '\n';
}