AT_arc092_d [ARC092F] Two Faced Edges

给定一个包含 $N$ 个顶点和 $M$ 条边的简单有向图。顶点编号为 $1, 2, \ldots, N$，边编号为 $1, 2, \ldots, M$。第 $i$ 条边从顶点 $a_i$ 指向顶点 $b_i$。 对于每一条边，判断如果将该边反向，图中的强连通分量的个数是否会发生变化。 这里，将第 $i$ 条边反向，指的是从图中删除该边，并添加一条从顶点 $b_i$ 指向顶点 $a_i$ 的新边。

输入通过标准输入给出，格式如下： > $N$ $M$ $a_1$ $b_1$ $a_2$ $b_2$ $\ldots$ $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 翻译