板子：

　　

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #include
          
            7 #include
           
             8 using namespace std; 9 #define maxn 10010 10 #define llg long long 11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout); 12 llg n,m,sett,father[maxn],pre[maxn],match[maxn],vis[maxn],id[maxn],dl[maxn*10],head,tail,ans; 13 14 vector
            
              a[maxn]; 15 16 llg find(llg x){ if (father[x]!=x) father[x]=find(father[x]); return father[x];} 17 18 llg lca(llg x,llg y) 19 { 20 sett++; 21 while (vis[x]!=sett) 22 { 23 if (x) 24 { 25 x=find(x); 26 if (vis[x]==sett) return x; 27 vis[x]=sett; 28 if (match[x]!=0) x=find(pre[match[x]]); 29 else x=0; 30 } 31 else 32 swap(x,y); 33 } 34 return x; 35 } 36 37 void change(llg x,llg y,llg fa) 38 { 39 llg z; 40 while (find(x)!=fa) 41 { 42 pre[x]=y; z=match[x]; 43 if (id[z]==1) {id[z]=0,dl[++tail]=z;} 44 father[z]=fa; 45 father[x]=fa; 46 y=z; x=pre[y]; 47 } 48 } 49 50 bool bfs(llg p) 51 { 52 llg x,w,v; 53 for (llg i=1;i<=n;i++) id[i]=-1,father[i]=i; 54 head=0,tail=1,dl[1]=p; id[p]=0; 55 do 56 { 57 x=dl[++head],w=a[x].size(); 58 for (llg i=0;i