rt

理论上是$O(nm)$的 在实际测评中跑出了5s喜提TLE的好成绩(

#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define MAXN 1005
#define MAXM 200005
#define ll long long
using namespace std;
int n,m;
int f[MAXN];
int q[MAXN],l;
int col[MAXN],low[MAXN],id[MAXN],cnt,colcnt;
int tot=1,head[MAXN];
bool vis[MAXN];
bool g[MAXN][MAXN];
struct edge{
	int from,to,next;
}e[MAXM];
void add(int u,int v)
{
	e[tot]=(edge){u,v,head[u]};
	head[u]=tot++;
}
inline void tarjan(int x)
{
	id[x]=low[x]=++cnt;
	q[++l]=x;
	for(int i=head[x];i;i=e[i].next)
	{
		int to=e[i].to;
		if(!id[to]) tarjan(to);
		if(col[to]) continue;
		low[x]=min(low[x],low[to]);
	}
	if(id[x]==low[x])
	{
		colcnt++;
		while(q[l+1]!=x)
			col[q[l--]]=colcnt;
	}
}
inline void dfs(int from,int now,int k,int w)
{
	if(vis[now]) return;
	vis[now]=1;
	if(!k) f[now]=w;
	else if(w!=f[now]) g[from][now]=1;
	for(int i=head[now];i;i=e[i].next)
		dfs(from,e[i].to,k,w);
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		add(u,v);
	}
	for(int i=1;i<=n;i++)
		if(!id[i])tarjan(i);
	for(int i=1;i<=n;i++)
	{
		int w=0;
		l=0;
		fill(vis+1,vis+1+n,0);
		vis[i]=1;
		for(int j=head[i];j;j=e[j].next)
			dfs(i,e[j].to,0,++w),q[++l]=e[j].to;
		fill(vis+1,vis+1+n,0);
		vis[i]=1;
		for(int j=l;j>=1;j--)
			dfs(i,q[j],1,w--);
	}
	for(int i=1;i<=m;i++)
		if(g[e[i].from][e[i].to]^(col[e[i].from]==col[e[i].to])) cout<<"diff\n";
		else cout<<"same\n";
	return 0;
}