#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define popcount __builtin_popcount using namespace std; typedef long long int ll; typedef pair P; struct HeavyLightDecomposition{ vector> g; vector in, out, rev, cnt, head, par; HeavyLightDecomposition(const vector> &g):g(g), in(g.size()), out(g.size()), rev(g.size()), cnt(g.size()), head(g.size()), par(g.size()){} void dfs_sz(int x, int p){ cnt[x]=1, par[x]=p; int mx=-1, k=-1; for(int i=0; i0) swap(g[x][k], g[x][0]); } void dfs_hld(int x, int p, int &t){ in[x]=t++; rev[in[x]]=x; for(int i=0; iin[v]) swap(u, v); if(head[u]==head[v]) return u; } } template T query(int u, int v, const F &f, const T &e, const Q &q, bool edge=false){//Tの型に注意 T ret=e; for(; ; v=par[head[v]]){ if(in[u]>in[v]) swap(u, v); if(head[u]==head[v]) break; ret=f(q(in[head[v]], in[v]+1), ret); } ret=f(q(in[u]+edge, in[v]+1), ret); return ret; } }; int main() { int n; cin>>n; vector> g(n); int a[200020], b[200020], c[200020]; for(int i=0; i>a[i]>>b[i]>>c[i]; a[i]--; b[i]--; g[a[i]].push_back(b[i]); g[b[i]].push_back(a[i]); } HeavyLightDecomposition hld(g); hld.build(); vector v(n+1); for(int i=0; i>q; while(q--){ int s, t; cin>>s>>t; s--; t--; cout<