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

## 예제 입력 1

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


## 예제 출력 1

4
2
4
4
2


## 출처

• 문제를 만든 사람: yclock

## 채점 및 기타 정보

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