是毒瘤的friends呢~

注意到“产生感情”和后缀自动机的$Right$集合定义很像，所以先对所有串建广义sam，那么一个节点$s$里的所有串都互相产生感情，而从起点走到$s$走最长路所经过的节点里的串都和$s$的串认识（因为是前缀关系）

所以这题其实是求用最少的仅在起点相交的链覆盖广义sam

把每个节点拆成两个点，连一条容量限制为$[1,1]$的边，对于所有原sam中的转移，连一条边$[0,1]$，最后新建一个汇点，把所有非起点的点连一条$[0,1]$到汇点，跑最小流即可

这样做保证每个点都仅被经过一次且路径不相交

关于上下界网络流，可以去看一看，这里不乱写了

p.s.dicnic加了优化真的是可以为所欲为的，不加就直接被kill掉，加了就100msA掉，代码中有注释符号的地方就是优化

#include
     
      #include
      
       #define inf 10000000int min(int a,int b){return a
       
        0){					dis[to[i]]=dis[x]+1;					if(to[i]==tt)return 1;//					tail++;					q[tail]=to[i];				}			}		}		return dis[tt]>0;	}	int dfs(int x,int flow){		if(x==tt)return flow;		int i,f;		for(i=cur[x];i;i=nex[i]){//			if(cap[i]>0&&dis[to[i]]==dis[x]+1){				f=dfs(to[i],min(flow,cap[i]));				if(f){					cap[i]-=f;					cap[i^1]+=f;					if(cap[i])cur[x]=i;//					return f;				}			}		}		dis[x]=-1;//		return 0;	}	int dicnic(){		int ans=0,tmp;		while(bfs()){			memcpy(cur,h,sizeof(h));//			while(tmp=dfs(ss,inf))ans+=tmp;		}		return ans;	}	void gao(){		dicnic();		eadd(t,s,inf,0);		s=dicnic();		for(int i=2;i<=M;i++){			if(ex[i]&&cap[i]!=0){				s=0;				break;			}		}		printf("%d",s);	}}namespace str{	struct sam{		int ch[1010],fa,v;	}t[10010];	int M=1;	int extend(int p,int c){		int q,nq;		if(t[p].ch[c]){			q=t[p].ch[c];			if(t[q].v==t[p].v+1)				return q;			else{				nq=++M;				t[nq]=t[q];				t[nq].v=t[p].v+1;				t[q].fa=nq;				while(p&&t[p].ch[c]==q){					t[p].ch[c]=nq;					p=t[p].fa;				}				return nq;			}		}else{			int np=++M;			t[np].v=t[p].v+1;			while(p&&t[p].ch[c]==0){				t[p].ch[c]=np;				p=t[p].fa;			}			if(p==0)				t[np].fa=1;			else{				q=t[p].ch[c];				if(t[q].v==t[p].v+1)					t[np].fa=q;				else{					nq=++M;					t[nq]=t[q];					t[nq].v=t[p].v+1;					t[np].fa=t[q].fa=nq;					while(p&&t[p].ch[c]==q){						t[p].ch[c]=nq;						p=t[p].fa;					}				}			}			return np;		}	}	int x[5010];	void gao(){		int k,m,n,i,j;		scanf("%d%d",&k,&m);		while(m--){			scanf("%d",&n);			i=1;			while(n--){				scanf("%d",&j);				i=extend(i,j);			}		}		gra::s=1;		gra::t=M+1;		gra::ss=M<<1|1;		gra::tt=(M<<1)+2;		for(i=1;i<=k;i++){			if(t[1].ch[i])gra::eadd(1,t[1].ch[i],inf,0);		}		for(i=2;i<=M;i++){			gra::eadd(gra::ss,i+M,1,1);			gra::eadd(i,gra::tt,1,1);			for(j=1;j<=k;j++){				if(t[i].ch[j])gra::eadd(i+M,t[i].ch[j],1,0);			}			gra::eadd(i+M,M+1,1,0);		}	}}int main(){	str::gao();	gra::gao();}