题目描述

给定一个包含 $N$ 个顶点和 $M$ 条边的简单有向图。顶点编号为 $1, 2, \dots, N$，边编号为 $1, 2, \dots, M$。第 $i$ 条边从顶点 $a_i$ 指向顶点 $b_i$。

对于每一条边，判断如果将该边反向，图中的强连通分量的个数是否会发生变化。

这里，将第 $i$ 条边反向，指的是从图中删除该边，并添加一条从顶点 $b_i$ 指向顶点 $a_i$ 的新边。

输入格式

输入通过标准输入给出，格式如下：

$N$ $M\\$ $a_1$ $b_1\\$ $a_2$ $b_2\\$ $\vdots\\$ $a_M$ $b_M$

输出格式

输出 $M$ 行。对于第 $i$ 条边，如果将其反向后强连通分量的个数发生变化，输出 diff，否则输出 same。

样例 1

输入

3 3
1 2
1 3
2 3

输出

same
diff
same

样例 2

输入

2 2
1 2
2 1

输出

diff
diff

样例 3

输入

5 9
3 2
3 1
4 1
4 2
3 5
5 3
3 4
1 2
2 5

输出

same
same
same
same
same
diff
diff
diff
diff

说明/提示

限制条件

• $2 \leq N \leq 1000$
• $1 \leq M \leq 200,\!000$
• $1 \leq a_i, b_i \leq N$
• $a_i \neq b_i$
• 如果 $i \neq j$，则 $a_i \neq a_j$ 或 $b_i \neq b_j$

样例解释 1

如果不反转任何边，强连通分量的个数为 $3$，但如果反转第 $2$ 条边，强连通分量的个数变为 $1$。

样例解释 2

反转边后，图中可能会出现重边。

由 ChatGPT 4.1 翻译