翻转有向图

题目限制

5000 ms 256 M

题目描述

给出了一个 $N$ 个点和 $M$ 条边的有向图。顶点编号为 $1\sim N$ 。图中没有重边和自环。

对于这 $M$ 条边，求如果仅反转这一条边，是否会对整个图的强连通分量的数量产生影响？

在这里，反转边 $i$ 的意思是一条点 $a$ 向 $b$ 的边，替换为从点 $b$ 向 $a$ 的边。

输入格式

第一行输入两个数N,M，分别表示图中点数和边数。（2≤N≤1000,1≤M≤2e5） 之后M行：每行两个数a,b，描述一条点a向b的连边。

输出格式

输出共M行，每行一个字符串表示答案。在第i行中，如果边i的反转会改变图中强连通分量的数量，则输出diff；如果不会，请输出same。

数据范围

对于 $24\%$ 的数据：$2 \le N \le 20, 1 \le M \le 100$

对于 $100\%$ 的数据：$2 \le N \le 1000, 1 \le M \le 200,000, 1 \le a_i, b_i \le N$

输入样例

3 3
1 2
1 3
2 3

输出样例

same
diff
same