//TLE #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; //input from stdin istream& operator >> (istream& is, vector& vec){for(int& val: vec) scanf("%d", &val); return is;} istream& operator >> (istream& is, vector& vec){for(long long& val: vec) scanf("%lld",/*"%I64d",*/ &val); return is;} istream& operator >> (istream& is, vector& vec){for(double& val: vec) scanf("%lf", &val); return is;} char buff[200000]; istream& operator >> (istream& is, vector& vec){for(string& val: vec) {scanf("%s", buff); val=buff;}; return is;} template istream& operator >> (istream& is, vector& vec){for(T& val: vec) is >> val; return is;} template istream& operator , (istream& is, T& val){ return is >> val;} template ostream& operator << (ostream& os, const vector& vec){for(int i=0; i ostream& operator , (ostream& os, const T& val){ return os << " " << val;} template ostream& operator >> (ostream& os, const T& val){ return os << " " << val;} bool is_kadomatsu(const vector& v){ if(v.size()!=3) return false; if(v[0]==v[1] || v[1]==v[2] || v[2]==v[0]) return false; return (v[0]v[2]) || (v[0]>v[1] && v[1]> n; vector a(n); cin >> a; vector> G(n); for(int i=0; i> u,v;*/scanf("%d%d",&u,&v); u--,v--; G[u].push_back(v); G[v].push_back(u); } vector depth(n, -1); vector> par(n, vector(20)); function dfs = [&](int pos, int last, int last2){ depth[pos] = depth[last]+1; par[pos][0] = last; for(int next : G[pos]){ if(next == last) continue; dfs(next, pos, last); } }; dfs(0,0,0); for(int k=1; k<20; k++){ for(int i=0; i>=1, i++) if(k&1) pos = par[pos][i]; return pos; }; auto lca = [&](int x, int y){ if(depth[x] < depth[y]) swap(x,y); x = kth_parent(x, depth[x] - depth[y]); if(x==y) return x; for(int k=19; k>=0; k--){ if(par[x][k] != par[y][k]){ x = par[x][k]; y = par[y][k]; } } return par[x][0]; }; int cnt = 0; int q; cin >> q; while(q--){ int u,v; /*cin >> u,v;*/ scanf("%d%d",&u,&v); u--,v--; assert(u!=v); int p = lca(u,v); bool ok = true; vector x,y; x.push_back(u); while(u != p){ u = par[u][0]; x.push_back( u ); } while(v != p){ y.push_back( v ); v = par[v][0]; } while(y.size()){ x.push_back( y.back() ); y.pop_back(); } for(int i=0; i