Score : 1100 points
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.
Input is given from Standard Input in the following format:
N M a_1 b_1 a_2 b_2 : a_M b_M
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
.
3 3 1 2 1 3 2 3
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.
2 2 1 2 2 1
diff diff
Reversion of an edge may result in multiple edges in the graph.
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