F - Two Faced Edges Editorial /

Time Limit: 5 sec / Memory Limit: 256 MB

配点 : 1100 点

問題文

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

Score : 1100 points

Problem Statement

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.

Sample Input 1

3 3
1 2
1 3
2 3

Sample Output 1

same
diff
same

The number of the strongly connected components is 3 without reversion of edges, but it will become 1 if Edge 2 is reversed.

Sample Input 2

2 2
1 2
2 1

Sample Output 2

diff
diff

Reversion of an edge may result in multiple edges in the graph.

Sample Input 3

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

Sample Output 3

same
same
same
same
same
diff
diff
diff
diff