← 返回题目列表

AtCoder · arc092_d

F. 两个面的边缘

中文机器翻译题面 查看原题

分数: 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