409543: GYM103627 G Critical Vertex

You are given a connected undirected graph $$$G$$$ with $$$N$$$ vertices and $$$M$$$ edges where vertices are numbered from $$$1$$$ to $$$N$$$ and edges are numbered from $$$1$$$ to $$$M$$$.

For each vertex $$$v$$$, if the graph is disconnected after the vertex $$$v$$$ is removed, we call $$$v$$$ a critical vertex. Note that the original connectedness of the graph does not matter.

For each $$$i$$$ ($$$1 \le i \le M$$$), please compute the number of critical vertices in $$$G$$$ when edge $$$i$$$ is removed. Note that the removal is only temporary, and does not affect other queries.

The first line contains two integers $$$N$$$ and $$$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$$$ and $$$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$$$). The graph may have multiple edges. The graph is connected.

Output $$$M$$$ lines. On the $$$i$$$-th line, output a single integer denoting the number of critical vertices in $$$G$$$ when edge $$$i$$$ is removed.

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

4
2
4
4
2