You are given a directed graph with N vertices and M edges. The vertices are numbered 1, 2, ..., N, and the edges are numbered 1, 2, ..., M. Edge i points from Vertex a_i to Vertex b_i.

For each edge, determine whether the reversion of that edge would change the number of the strongly connected components in the graph.

Here, the reversion of Edge i means deleting Edge i and then adding a new edge that points from Vertex b_i to Vertex a_i.

Constraints

• $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$, then $a_i \neq a_j$ or $b_i \neq b_j$.

Input

Input is given from Standard Input in the following format:

N M
a_1 b_1
a_2 b_2
:
a_M b_M

Output

Print M lines. In the i-th line, if the reversion of Edge i would change the number of the strongly connected components in the graph, print diff; if it would not, print same.

Examples

Input

3 3
1 2
1 3
2 3

Output

same
diff
same

Input

2 2
1 2
2 1

Output

diff
diff

Input

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

Output

same
same
same
same
same
diff
diff
diff
diff

见题面

见题面