思路是只计算每个人一血将要杀别人时杀他的贡献，方案数是区间长度。

#include<cstdio>
#include<cstring>
#include<cctype>

#define re register
#define il inline

il int read()
{
	re int x=0;
	char ch=getchar();
	while(!isdigit(ch)) ch=getchar();
	while(isdigit(ch))
	{
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x;
}

const int N=6e4+5,M=1e3+5;

int n,m;
int u[N],v[N];
int h[M],th[M];
int r,ans[M];//r是不操作时最终存活人数

void reseth()
{
	for(int i=1;i<=m;++i)
		h[i]=3;
}
void resett()
{
	for(int i=1;i<=m;++i)
		th[i]=3;
}
int cal(int t,int s)
{
	resett();
	int res=m;
	for(int k=1;k<=n;++k)
	{
		if(th[u[k]]&&th[v[k]])
		{
			th[v[k]]--;
			if(!th[v[k]]) res--;
		}
		if(k==t-1)
			th[s]--,res--;
	}
//	printf("cal(%d,%d)=%d\n",t,s,res);
	return res;
}

int main()
{
	n=read(),m=read();
	reseth();
	r=m;
	for(int i=1;i<=n;++i)
	{
		u[i]=read(),v[i]=read();
		if(h[u[i]]&&h[v[i]])
		{
			h[v[i]]--;
			if(!h[v[i]]) r--;
		}
	}
	for(int i=1;i<=m;++i)
	{
		int pre=0;
		reseth();
		for(int k=1;k<=n;++k)
		{
			if(h[u[k]]&&h[v[k]])
				h[v[k]]--;
			if(h[i]==1&&u[k]==i)
			{
				ans[cal(k,i)]+=k-pre;
				pre=k;
			}
		}
		if(h[i]==1) ans[r-1]+=n+1-pre;
		if(!h[i]||h[i]>1) ans[r]+=n+1-pre;
	}
	for(int i=0;i<=m;++i)
		printf("%d ",ans[i]);
	return 0;
}

甚至过了自己的手造样例：

3 9
1 2
1 2
2 3
2 3
3 1
3 1
1 2
2 3
3 1