시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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.

서브태스크 1 (5점)

  • $N \le 200$
  • $M \le 500$

서브태스크 2 (11점)

  • $N \le 1\,000$
  • $M \le 2\,500$

서브태스크 3 (7점)

  • $N = M$

서브태스크 4 (13점)

  • For each edge $e$, there exists at most one simple cycle containing $e$.

서브태스크 5 (25점)

  • $N \le 8\,000$
  • $M \le 250\,000$

서브태스크 6 (29점)

  • $N \le 100\,000$
  • $M \le 250\,000$

서브태스크 7 (10점)

  • No additional limits.

예제 입력 1

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

예제 출력 1

4
2
4
4
2

출처

  • 문제를 만든 사람: yclock

채점 및 기타 정보

  • 예제는 채점하지 않는다.
  • 이 문제의 채점 우선 순위는 2이다.