시리얼

시간 제한1초메모리 제한512 MB

요약

소들이 좋아하는 시리얼과 두 번째로 좋아하는 시리얼이 주어질 때, 앞에서 i마리를 제거했을 때 시리얼을 받는 소의 수를 모든 i에 대해 구한다.

난이도: 어려움10점 중 9점
유형: 그리디, 시뮬레이션, 구현, 그래프
정답자: 아직 제출이 없습니다

문제

Farmer John의 소들은 아침으로 시리얼을 먹는 것을 무엇보다 좋아한다! 사실 소들의 식욕이 너무 커서, 한 끼에 시리얼 한 상자를 통째로 먹는다.

농장에 $M$ 가지 종류의 시리얼이 담긴 배송품이 도착했다 $(1\le M\le 10^5)$ . 안타깝게도 각 시리얼은 상자가 하나뿐이다! $N$ 마리의 소 $(1\le N\le 10^5)$ 는 각각 가장 좋아하는 시리얼과 두 번째로 좋아하는 시리얼이 있다. 선택할 수 있는 시리얼이 주어지면, 소는 다음 과정을 따른다:

가장 좋아하는 시리얼의 상자가 아직 남아 있으면, 그것을 가져가고 떠난다.
그렇지 않고 두 번째로 좋아하는 시리얼의 상자가 아직 남아 있으면, 그것을 가져가고 떠난다.
그렇지 않으면, 실망하며 울음소리를 내고 아무 시리얼도 가져가지 않은 채 떠난다.

소들은 시리얼을 받기 위해 줄을 섰다. 각 $0 \leq i \leq N-1$ 에 대해, Farmer John이 줄에서 앞의 $i$ 마리의 소를 제거했을 때 시리얼 상자를 가져가는 소가 몇 마리인지 구하라.

입력

첫째 줄에 공백으로 구분된 두 정수 $N$ 과 $M$ 이 주어진다.

각 $1\le i\le N$ 에 대해, $i$ 번째 줄에 $i$ 번째로 줄을 선 소가 가장 좋아하는 시리얼과 두 번째로 좋아하는 시리얼을 나타내는 두 정수 $f_i$ 와 $s_i$ 가 공백으로 구분되어 주어진다 ( $1\le f_i,s_i\le M$ 이고 $f_i\neq s_i$ ).

출력

각 $0\le i\le N-1$ 에 대해, $i$ 에 대한 답을 한 줄에 하나씩 출력한다.

힌트

소가 적어도 두 마리 남아 있다면, 그중 정확히 두 마리가 시리얼 상자를 가져간다.

예제1

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