这题看上去像 AC 自动机或者 KMP 的样子，但是整个串就 $2$ 个字符那就可以变成一个图了。

建完图后易发现一个连通分量里的串一定可以通过某种连接方式串到一个串里，故缩点。

然后就是 DAG 最小路径覆盖数了，参考这道题。

但是那题条件是单点只能被一条路径覆盖，所以我们再用 Floyd 解决这个问题（实际上就是这道题了）。

我用的是最最最复杂的 tarjan 和网络流，而且 Floyd 好像写挂了让 Qwen 改成了 bitset，将就着用吧。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1010,M=1e5+10;
vector<int>G[N],G2[N],V[N];
int tsp,cnt,scc[N],low[N],dfn[N],rd[N],siz[N];
stack<int>stk;bool instk[N];
void tarjan(int x)
{
    low[x]=dfn[x]=++tsp;
    stk.push(x);instk[x]=true;
    for(int y:G[x])
    {
        if(dfn[y]==0)
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else if(instk[y]==true)low[x]=min(low[x],dfn[y]);
    }
    if(low[x]==dfn[x])
    {
        cnt++;
        for(int z=-1;z!=x;)
        {
           z=stk.top();stk.pop();instk[z]=false;
           scc[z]=cnt;siz[cnt]++;
        }
    }
} 
string s[N];
struct node{int to,v,nxt;}e[M];int head[M],len;
void add(int x,int y,int c)
{
	e[++len]={y,c,head[x]};head[x]=len;
	e[++len]={x,0,head[y]};head[y]=len;	
}
int cur[N],d[N],st,ed;
bool find()
{
	memset(d,0,sizeof(d));d[st]=1;
	deque<int>q;q.push_back(st);
	while(!q.empty())
	{
		int x=q.front();q.pop_front();
		for(int i=head[x];i;i=e[i].nxt)
		{
			int y=e[i].to;
			if(d[y]==0&&e[i].v)
			{
				d[y]=d[x]+1;
				q.push_back(y);
				if(y==ed)return 1;
			}
		}
	}
	return 0;
}
int flow(int x,int s)
{
	if(x==ed)return s;
	int ans=0;
	for(int i=cur[x];i;i=e[i].nxt)
	{
		int y=e[i].to;
		cur[x]=i;
		if(d[y]==d[x]+1&&e[i].v)
		{
			int sum=flow(y,min(e[i].v,s));
			e[i].v-=sum;
			e[i^1].v+=sum;
			ans+=sum;
			s-=sum;
			if(s==0)break;
		}
	}
	if(ans==0)d[x]=0;
	return ans;
}
int dinic()
{
	int ans=0;
	while(find())
	{
		memcpy(cur,head,sizeof(cur));
		ans+=flow(st,1e18);
	}
	return ans;
}
bitset<N>v[N];
signed main()
{
	int n;cin>>n;
	for(int i=1;i<=n;i++)cin>>s[i];
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(i!=j&&s[i][1]==s[j][0])G[i].push_back(j);
	for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
	st=0,len=1,ed=cnt*2+1;
	for(int i=1;i<=cnt;i++)add(st,i,1);
	for(int i=1;i<=cnt;i++)add(i+cnt,ed,1);
	for(int i=1;i<=n;i++)for(int j:G[i])
	{
		int x=scc[i],y=scc[j];
		if(x!=y)v[x][y]=1;
	}
	for(int k=1;k<=cnt;k++)
		for(int i=1;i<=cnt;i++)
			if(i!=k&&v[i][k])v[i]|=v[k];
	for(int i=1;i<=cnt;i++)for(int j=1;j<=cnt;j++)if(i!=j&&v[i][j])
		add(i,j+cnt,1);
	int ans=cnt-dinic();
	cout<<ans;
	return 0;
}