|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|2.5 초||1024 MB||9||4||3||37.500%|
You are given a connected undirected graph $G$ with $N$ vertices and $M$ edges where each vertices are numbered from $1$ to $N$ and each edges are numbered from $1$ to $M$.
For each vertices $v$, if the removal of vertex $v$ causes the graph to be disconnected, we call $v$ as a critical vertex.
For each $i$ ($1 \le i \le M$), please compute the number of critical vertex in $G$ when edge $i$ is removed. Note that the removal is only temporary, and does not affect future queries.
The first line of the input contains two integers $N, M$. ($2 \le N \le 250\,000$, $1 \le M \le 1\,000\,000$)
In the next $M$ lines, edges of the graph will be given. The $i$-th line contains two integers $x_i, y_i$, denoting the edge $i$ connecting vertex $x_i$ and vertex $y_i$. ($1 \le x_i, y_i \le N, x_i \neq y_i$).
Multiple edges connecting the same pair of vertices may exist.
The given graph is connected.
Print $M$ lines. In the $i$-th line, print a single integer denoting the number of critical vertex in $G$ when edge $i$ is removed.
5 5 1 5 5 2 2 3 2 4 2 5
4 2 4 4 2