実行時間制限: 5 sec / メモリ制限: 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