#include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long int LL; typedef pair P; typedef pair LP; const int INF=1<<30; const LL MAX=1e9+7; void array_show(int *array,int array_n,char middle=' '){ for(int i=0;i &vec_s,int vec_n=-1,char middle=' '){ if(vec_n==-1)vec_n=vec_s.size(); for(int i=0;i &vec_s,int vec_n=-1,char middle=' '){ if(vec_n==-1)vec_n=vec_s.size(); for(int i=0;i uft_q1; vector uft_parent; vector uft_num; public: void init(int uft_n){ uft_parent.assign(uft_n,-1); uft_num.assign(uft_n,0); } union_find_tree(int uft_n){ init(uft_n); } union_find_tree(){ init(uft_N); } int check_parent(int uft_x){ if(uft_parent[uft_x]!=-1){ uft_q1.push(uft_x); return check_parent(uft_parent[uft_x]); } int uft_a; while(!uft_q1.empty()){ uft_a=uft_q1.front(),uft_q1.pop(); uft_parent[uft_a]=uft_x; } return uft_x; } bool connect(int uft_x,int uft_y){ uft_x=check_parent(uft_x),uft_y=check_parent(uft_y); if(uft_x==uft_y)return true; if(uft_num[uft_x]>uft_num[uft_y])swap(uft_x,uft_y); uft_parent[uft_x]=uft_y; uft_num[uft_y]+=uft_num[uft_x]; return false; } }; int num[110000]; int main(){ int n,m; int i,j,k; int a,b,c; cin>>n; union_find_tree ua(n); int flag=0; for(i=0;i>a>>b; if(ua.connect(a,b))flag++; num[a]++,num[b]++; } if(flag==1){ flag=0; for(i=0;i