orz ymx，ymx ddw %%%
首先既然题目要我们判断强连通分量个数是否改变，我们首先就将原图 SCC 缩个点呗，缩完点后我们很自然地将图中的边分为两类：在某个强连通分量中，和不在强连通分量中，我们对这两个情况分别进行讨论。
下面又到了喜闻乐见的找性质的时间了。首先，对于不在同一个强连通分量中的边，把它翻转之后不会影响强连通分量个数，因为这条边不在强连通分量里面，即便把它断掉也不影响强连通分量内部的点的可达性，因此把它翻转只可能接链成环，减少强连通分量个数，而把 (u o v) 翻转后，强连通分量个数减少当且仅当去掉这条边后仍存在 (u o v) 的路径，因为这样会出现 (u o v o u) 的环。其次，对于在同一个强连通分量中的边，把它翻转之后，本来不能到达的点依然不能到达（证明可考虑反证法，对于两个节点 (x,y)，如果本来不存在 (x o y)，翻转 (u o v) 后就存在了，那么必然是因为存在 (x o v o u o y) 的路径，而根据 (u,v) 在同一个 SCC 中可知本来就存在 (v o u) 的路径 (P)（我们记其为 (xxrightarrow{P}y)），那么必然存在不经过边 (v o u) 的 (x o y) 的路径 (x o vxrightarrow{P}u o y)，矛盾），而对于原来可以到达的两个点 (x,y)，如果翻转后 (x) 不能到达 (y)，那必然有 (x,y) 在同一个连通分量中，此时连通分量的个数就会改变。我们惊奇地发现，在两种情况中，虽然情况细分起来不一样，但每种情况我们要求的目标是一样的，即去掉某条边 (u o v) 后，(u) 是否还能到达 (v)。对于 (u,v) 在同一个强连通分量中的边 ((u,v))，如果上述回答为肯定的那么答案即为 same，否则答案为 diff，如果 (u,v) 不在同一个强连通分量则反过来。
接下来考虑怎样求这个东西，考虑枚举 (u) 并求出以 (u) 为起点的所有边的答案，我们将以 (u) 为起点的边按照编号（其实不一定要按编号，哪怕 random_shuffle 一下都行，只要钦定一个顺序即可）排序分别为 (e_1,e_2,cdots,e_k)，它们的另一个端点分别为 (v_1,v_2,cdots,v_k)。我们从小到大依次枚举这些边并实时维护一个 (vis_x) 表示 (x) 的可达性，对于某个 (e_i)，如果我们发现，枚举到 (e_i) 时候，已经有 (vis_{v_i}=1)，那么说明肯定存在一个 (v_j) 满足存在 (u o v_j o v_i) 的路径，即去掉这条边后 (u) 还能到达 (v_i)，否则我们就以 (v_i) 为起点 BFS 一遍整张图，找到所有可达的点，注意不能经过 (u)，否则就无法说明是否经过 (u o v_i) 的边了。（具体实现方法很简单，只需将 (vis_u) 设为 (1)，然后 BFS 所有 (vis_v
e 1) 的点）这样我们只考虑了 (e_j) 对 (e_i)，(j<i) 的贡献，因此还需反过来再操作一次，这样即可考虑所有边对 (v_i) 的贡献，正确性显然，时间复杂度 (nm)，可以通过此题，于是这题就做完了。
什么？你说做完了？如果 (m) 增大到 (10^6) 恐怕你就束手无策了吧……因此我们还需探究复杂度更优的做法，注意到上述做法的瓶颈在于每次 BFS 都枚举了每条边，使得 BFS 的复杂度高达 (mathcal O(m))，事实上，如果当我们 BFS 到某个点 (u) 时，只继续 BFS 它的邻居中满足 (vis_v=0) 的点 (v)，这样 BFS 复杂度可以降到 (mathcal O(n))。那么怎么快速找出这些点呢？注意 (vis_v) 的取值只可能是 (0/1)，因此可以联想到常数巨小无比的……bitset！我们建一个 bitset (t)，如果 (vis_v=1)，那么 bitset 上对应位为 (0)，否则为 (1)，再对每个点维护它与每个点之间是否有直接边相连，记作 (has_x)，那么当我们 BFS (u) 时，只需遍历 (has_u&t) 上为 (1) 的位即可。事实上，bitset 找出所有 (1) 的复杂度是 (mathcal O(dfrac{n}{omega})) 的，可以这样实现：
for(int y=b._Find_first();y^b.size();y=b._Find_next(y))
于是这题就真的做完了，复杂度 (dfrac{n^3}{omega}+w)，瓶颈在于 bitset 的遍历。
const int MAXN=1e3;
const int MAXM=2e5;
int n,m,hd[MAXN+5],to[MAXM+5],nxt[MAXM+5],ec=0;
int U[MAXM+5],V[MAXM+5];
void adde(int u,int v){to[++ec]=v;nxt[ec]=hd[u];hd[u]=ec;}
bool vis[MAXN+5];
int dfn[MAXN+5],low[MAXN+5],tim=0,bel[MAXN+5],stk[MAXN+5],tp=0,cmp=0;
bitset<MAXN+5> has[MAXN+5];
void tarjan(int x){
dfn[x]=low[x]=++tim;vis[x]=1;stk[++tp]=x;
for(int e=hd[x];e;e=nxt[e]){
int y=to[e];
if(!dfn[y]) tarjan(y),low[x]=min(low[x],low[y]);
else if(vis[y]) low[x]=min(low[x],dfn[y]);
} if(!(dfn[x]^low[x])){
++cmp;int o;do{
o=stk[tp--];vis[o]=0;bel[o]=cmp;
} while(o^x);
}
}
bool can[MAXM+5];
bitset<MAXN+5> alive;
void bfs(int s){
queue<int> q;q.push(s);alive.reset(s);
while(!q.empty()){
int x=q.front();q.pop();bitset<MAXN+5> to=has[x]&alive;
for(int y=to._Find_first();y^to.size();y=to._Find_next(y))
alive.reset(y),q.push(y);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&U[i],&V[i]);adde(U[i],V[i]);
has[U[i]].set(V[i]);
}
for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);
// for(int i=1;i<=n;i++) printf("%d
",bel[i]);
for(int i=1;i<=n;i++){
alive.set();alive.reset(i);stack<pii> stk;
for(int e=hd[i];e;e=nxt[e]){
stk.push(mp(to[e],e));
if(!alive.test(to[e])){can[e]=1;continue;}
bfs(to[e]);
} alive.set();alive.reset(i);
while(!stk.empty()){
pii x=stk.top();stk.pop();
if(!alive.test(x.fi)){can[x.se]=1;continue;}
bfs(x.fi);
}
}
for(int i=1;i<=m;i++) printf("%s
",((bel[U[i]]==bel[V[i]])^can[i])?"diff":"same");
return 0;
}