Description

有n 个人参加Revue，她们之间共进行了m 场比赛

如果在某场比赛中a 击败了b，那么a 可能胜过b

如果a 可能胜过b，b 可能胜过c，那么a 可能胜过c

如果x 可能胜过y，y 也可能胜过x，那么x 和y 是旗鼓相当的

但如果x 可能胜过y 不满足，y 可能胜过x 也不满足，那么x 和y 不是旗鼓相当的

可以发现，如果a 和b 是旗鼓相当的，b 和c 是旗鼓相当的，那么a 和c 也是旗鼓相当的。也就是

说，若干个旗鼓相当的人组成了一个群体，群体之内任意两个人是旗鼓相当的，不同群体的任意两个人肯

定不是旗鼓相当的。

现在，对于每一场比赛，星见班长想知道，如果这场比赛的胜负改变了的话，群体情况会不会也跟着

发生改变。群体情况改变，当且仅当存在两个人，一开始在一个群体，胜负改变后不在一个群体；或者一

开始不在一个群体，胜负改变后在一个群体。

注： 出题人被咕了 导致大数据丢失 且该题有O（n^2）的做法

Input Format

Input

第一行两个正整数n,m，表示有n 个人和m 场比赛

接下来m 行，每行两个正整数a, b 描述一场比赛，这场比赛中a 击败了b

Output Format

Output

m 行，每行一个字符串表示这场比赛胜负改变后群体情况会不会改变

改变输出”diff”，不改变输出”same”(不包括引号)

Sample

样例1：

输入：

3 3
1 2
1 3
2 3

输出：

same
diff
same

样例2：

输入：

5 9
3 2
3 1
4 1
4 2
3 5
5 3
3 4
1 2
2 5

输出：

same
same
same
same
same
diff
diff
diff
diff

Hint

对于所有数据，满足2 ≤ n ≤ 103 , 1 ≤ m ≤ 2 ∗ 105，没有两次比赛参加的人相同，胜负也相同

Subtask1[31pts] n ≤ 100,m ≤ 500

Subtask2[12pts] m = n − 1，保证把有向边看作无向边后，原图联通

Subtask3[17pts] m = n，保证把有向边看作无向边后，原图联通

Subtask4[18pts] m ≤ 5000

Subtask5[22pts] 无特殊限制