题目描述

给定一个有 $N$ 个顶点和 $M$ 条边的有向图。顶点编号为 $1, 2, ..., N$，边的编号为 $1, 2, ..., M$。边 $i$ 起始于顶点 $a_i$，终止于顶点 $b_i$。

对于每条边，判断将该边反向是否会改变图中强连通分量的数量。

这里，边 $i$ 反向的意思是删除边 $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$
• 如果 $i \neq j$，则 $a_i \neq a_j$ 或 $b_i \neq b_j$。

输入

从标准输入读入输入数据。输入格式如下：

$N$ $M$ $a_1$ $b_1$ $a_2$ $b_2$ $:$ $a_M$ $b_M$

输出

打印 $M$ 行。第 $i$ 行中，如果将边 $i$ 反向会改变图中强连通分量的数量，则打印 diff；如果不会改变，则打印 same。

示例输入 1

3 3
1 2
1 3
2 3

示例输出 1

same
diff
same

在不反向边的情况下，强连通分量的数量为 $3$。但是如果反向边 $2$，则数量将变为 $1$。

示例输入 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