该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在远古的沉睡之城中，有 $N$ 个废弃的宫殿和 $M$ 条神秘的秘密通道，这些通道连接着不同的宫殿。每个宫殿都有一个独特的编号，从 $1\sim N$。这些秘密通道是单向的，意味着每条通道都是从一个宫殿通向另一个宫殿，城中不存在两条相同的通道，也没有任何通道指向自己。

传说，这些秘密通道隐藏着开启沉睡之城宝藏的秘密。有一位勇敢的探险家试图解开这个秘密，他发现通过改变某些通道的方向，可能会揭示新的秘密或保持一切不变。

对于这 $M$ 条秘密通道，探险家想知道，如果他只改变一条通道的方向，是否会对整个沉睡之城的强连通分量的数量产生影响？

在这里，改变通道的方向意味着如果原本从宫殿 $a$ 通向宫殿 $b$ 的通道，现在将改为从宫殿 $b$ 通向宫殿 $a$。

输入格式

第一行输入两个数 $N,M$，分别表示沉睡之城中的宫殿数和秘密通道数。

接下来的 $M$ 行：每行两个数 $a,b$，描述一条从宫殿 $a$ 通向宫殿 $b$ 的秘密通道。

输出格式

输出共 $M$ 行，每行一个字符串表示答案。 在第 $i$ 行中，如果通道 $i$ 的方向改变会影响强连通分量的数量，则输出 diff；如果不会，请输出 same。

样例描述

输入1

3 3
1 2
1 3
2 3

输出1

same
diff
same

数据范围描述

对于 $24\%$ 的数据：$2 \le N \le 20, 1 \le M \le 100$

对于 $100\%$ 的数据：$2 \le N \le 1000, 1 \le M \le 200,000, 1 \le a_i, b_i \le N$