#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define N (1000000000+7) //#define N 998244353 #define INF 1e16 typedef long long ll; typedef pair P; const int inf = 1e8; class UnionFind { public: vectorpar, rank, node; UnionFind(int n) :par(n), rank(n, 0),node(n,1) { for (int i = 0;i < n;i++)par[i] = i; } void init(int n) { for (int i = 0;i < n;i++) { par[i] = i; rank[i] = 0; node[i] = 1; } } int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); } bool same(int x, int y) { return find(x) == find(y); } void unite_tree(int x, int y) { x = find(x); y = find(y); if (x == y)return; if (rank[x] < rank[y]) { par[x] = y; } else { par[y] = x; if (rank[x] == rank[y])rank[x]++; } } int root_size(int x){ return rank[find(x)]; } int size(int x) { return node[find(x)]; } void unite_node(int x, int y) { x = find(x); y = find(y); if (x == y)return; if (size(x) < size(y))swap(x, y); node[x] += node[y]; par[y] = par[x]; } }; int main() { int n; cin>>n; UnionFind uf = UnionFind(n); for(int i=0;i>u>>v; uf.unite_node(u,v); } int Size = 0; for(int i=0;i