{"problem":{"name":"Two Faced Edges","description":{"content":"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$. ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":5000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc092_d"},"statements":[{"statement_type":"Markdown","content":"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$.\nFor each edge, determine whether the reversion of that edge would change the number of the strongly connected components in the graph.\nHere, 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$.\n\n## Constraints\n\n*   $2 \\leq N \\leq 1000$\n*   $1 \\leq M \\leq 200,000$\n*   $1 \\leq a_i, b_i \\leq N$\n*   $a_i \\neq b_i$\n*   If $i \\neq j$, then $a_i \\neq a_j$ or $b_i \\neq b_j$.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$a_1$ $b_1$\n$a_2$ $b_2$\n$:$\n$a_M$ $b_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc092_d","tags":[],"sample_group":[["3 3\n1 2\n1 3\n2 3","same\ndiff\nsame\n\nThe number of the strongly connected components is $3$ without reversion of edges, but it will become $1$ if Edge $2$ is reversed."],["2 2\n1 2\n2 1","diff\ndiff\n\nReversion of an edge may result in multiple edges in the graph."],["5 9\n3 2\n3 1\n4 1\n4 2\n3 5\n5 3\n3 4\n1 2\n2 5","same\nsame\nsame\nsame\nsame\ndiff\ndiff\ndiff\ndiff"]],"created_at":"2026-03-03 11:01:14"}}