#include #include #include #include #include #include #include #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 q1; vector parent; vector num; public: void init(){ parent.assign(n,-1); num.assign(n,1); } union_find_tree(int n_init){ assert(n_init>=0); n=n_init; init(); } union_find_tree(){ n=N; init(); } int check_parent(int x){ assert(x>=0 && x=0 && x=0 && ynum[y])swap(x,y); parent[x]=y; num[y]+=num[x]; return false; } int size(int pos){ pos=check_parent(pos); return num[pos]; } }; namespace sol{ void solve(){ int n,m; int i,j,k; int a,b,c; cin>>n>>m; vector> v1(m); set s1,s2; for(i=0;i>a>>b; a--,b--; v1[a].push_back(b); s1.insert(b); } union_find_tree ua(n); int s=0; for(auto& v:v1){ if(v.size()>0)s++; if(v.size()<=1)continue; a=v[0]; for(i=1;i