#include using namespace std; #include #include #include #include #include template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } #define rep(i,n) for (int i = 0; i < (n); ++i) typedef long long ll; typedef unsigned long long ull; using P=pair; const ll INF=1e18; const int mod=998244353; struct Unionfind{ vectord; Unionfind(int n):d(n,-1){} int root(int x){ if(d[x]<0){return x;} return d[x]=root(d[x]); } bool unite(int x,int y){ x=root(x);y=root(y); if(x==y){return false;} if(d[x]>d[y]){swap(x,y);} d[x]+=d[y]; d[y]=x; return true; } bool same(int x,int y){return root(x)==root(y);} int size(int x){return -d[root(x)];} }; void solve(){ int n; cin>>n; Unionfind uf(n); vectorcnt(n); vectora(n),b(n); vectorused(n),ans(n); rep(i,n){ cin>>a[i]>>b[i]; a[i]--;b[i]--; uf.unite(a[i],b[i]); if(a[i]==b[i]){ans[i]=a[i]; used[a[i]]=1; } } rep(i,n){cnt[uf.root(a[i])]++;} rep(i,n){ if(uf.root(i)==i){ if(cnt[uf.root(i)]