分数: 1100 点
问题陈述
给你一个有向图 N 顶点和 M 边缘。 顶点已编号 1, 2, ..., N,并且边缘已编号 1, 2, ..., M。 边缘 i 来自顶点的点 a_i 到顶点 b_i.
对于每条边,确定该边的反转是否会改变图中强连通分量的数量。
这里,Edge 的回归 i 表示删除Edge i ,然后添加一条从顶点指向的新边 b_i 到顶点 a_i.
约束
- 2 \leq N \leq 1000
- 1 \leq M \leq 200,000
- 1 \leq a_i, b_i \leq N
- a_i \neq b_i
- If i \neq j,那么 a_i \neq a_j or b_i \neq b_j.
输入
输入由标准输入按以下格式给出:
N M a_1 b_1 a_2 b_2 : a_M b_M
输出
打印 M 行。在 i-第行,如果 Edge 的还原 i 会改变图中强连通分量的数量,打印 diff;如果没有,请打印 same.
示例输入 1
3 3 1 2 1 3 2 3
示例输出 1
same diff same
强连通分量的数量为 3 没有边缘反转,但它会变成 1 如果边缘 2 被颠倒。
示例输入 2
2 2 1 2 2 1
示例输出 2
diff diff
边的反转可能会导致图中出现多条边。
示例输入 3
5 9 3 2 3 1 4 1 4 2 3 5 5 3 3 4 1 2 2 5
示例输出 3
same same same same same diff diff diff diff