AT_arc092_d.[ARC092F] Two Faced Edges

给定一个包含 $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。

限制条件

• $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 翻译