하이퍼웨이

시간 제한3초메모리 제한1024 MB

요약

다중 그래프에 간선을 하나씩 추가할 때마다, 사이클에 속하게 되어 안전해진 간선의 개수를 매번 출력한다.

난이도: 어려움10점 중 8점
유형: 유니온 파인드, 그래프, DFS, 구현
정답자: 아직 제출이 없습니다

문제

은하 기업 Oods&co가 우리 은하의 행성을 잇는 하이퍼웨이 망을 건설한다. 건설 계획은 이미 준비되어 있고, 하이퍼웨이를 놓는 순서가 그 계획에 들어 있다. 하이퍼웨이 하나는 두 행성을 잇는 양방향 통로이며, 두 끝이 같은 행성일 수도 있다.

하이퍼웨이 $H$ 가 안전하지 않다는 것은, $A$ 에서 $B$ 로 가려면 반드시 $H$ 를 지나야 하는 두 행성 $A$ , $B$ 가 있다는 뜻이다. 그런 행성 쌍이 없으면 $H$ 는 안전하다. 즉 (직접 또는 간접으로) 어떤 행성 쌍을 잇는 유일한 하이퍼웨이가 아니면 안전하다. 안전한 하이퍼웨이는 어떤 사이클 위에 놓인 하이퍼웨이와 정확히 같다.

하이퍼웨이를 놓는 순서가 주어진다. 하이퍼웨이를 하나 놓을 때마다 그 직후에 새로 안전해진 하이퍼웨이가 있을 수 있고, 방금 놓은 하이퍼웨이 자신도 거기에 포함될 수 있다. 건설마다 새로 안전해진 하이퍼웨이의 개수를 세라. 한 번 안전해진 하이퍼웨이는 공사가 끝날 때까지 계속 안전하다.

입력

첫째 줄에 두 정수 $n$ 과 $m$ 이 주어진다. $n$ 은 계획에 들어 있는 행성의 수, $m$ 은 하이퍼웨이의 수다. 행성의 번호는 $1$ 부터 $n$ 까지다.

다음 $m$ 개의 줄에는 각각 공백으로 구분된 두 정수가 주어진다. 다음으로 놓을 하이퍼웨이가 잇는 두 행성의 번호다. 한 행성을 자기 자신과 잇는 하이퍼웨이도 있을 수 있고, 같은 두 행성을 잇는 하이퍼웨이가 여러 개 있을 수도 있다.

모든 입력에서 $1 \le n \le 10^6$ , $1 \le m \le 2 \times 10^6$ 이다.

출력

입력에 주어진 각 하이퍼웨이에 대해, 그 하이퍼웨이를 놓은 직후 새로 안전해진 하이퍼웨이의 개수를 한 줄에 하나씩 출력한다.

예제6

예제 1

입력

예상 출력

예제 2
입력
```
1 3
1 1
1 1
1 1
```
예상 출력
```
1
1
1
```
예제 3
입력
```
2 4
1 2
1 2
1 2
2 2
```
예상 출력
```
0
2
1
1
```

예제 4

입력

예상 출력

예제 5
입력
```
6 5
1 2
1 3
1 4
1 5
1 6
```
예상 출력
```
0
0
0
0
0
```
예제 6
입력
```
8 3
1 2
2 1
7 7
```
예상 출력
```
0
2
1
```