#include #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; using namespace atcoder; typedef long long ll; typedef pair P; struct unionfind{ vector par, sz; unionfind() {} unionfind(int n):par(n), sz(n, 1){ for(int i=0; isz[y]) swap(x, y); par[x]=y; sz[y]+=sz[x]; } bool same(int x, int y){ return find(x)==find(y); } int size(int x){ return sz[find(x)]; } }; int main() { int n; cin>>n; int a[100010], b[100010]; unionfind uf(n); bool ok[100010]={}; for(int i=0; i>a[i]>>b[i]; a[i]--; b[i]--; if(uf.same(a[i], b[i])){ ok[i]=1; } uf.unite(a[i], b[i]); } int c[100010]={}, e[100010]={}; for(int i=0; i g[100010]; int i0; bool used[100010]={}; int ans[100010]; auto dfs=[&](auto dfs, int x)->void{ used[x]=1; for(auto q:g[x]){ if(i0==q.second || used[q.first]) continue; int y=q.first; dfs(dfs, y); ans[q.second]=y; } }; for(int i=0; i