페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#3703

시리얼 1초 256MB

문제

농부 창호의 소들이 가장 좋아하는 아침식사 메뉴는 시리얼이다.

소들은 덩치가 크기 때문에, 한 끼에 시리얼 한 박스를 먹는다.

농부 창호의 목장에서는 최근 M박스의 시리얼을 받았다. 

불행히도, M개의 시리얼은 모두 종류가 달랐다! 

농부 창호의 N마리의 소들은 가장 좋아하는 시리얼과, 그 다음으로 좋아하는 시리얼이 있다. 

 

소들에게 시리얼 선택지를 보여주면 다음과 같은 과정에 의해 시리얼을 선택한다.

  1. 자신이 가장 좋아하는 시리얼이 선택되지 않았다면, 그 시리얼을 택한다.

  2. 가장 좋아하는 시리얼을 이미 다른 소가 선택했고, 두 번째로 좋아하는 시리얼이 남아있다면, 그 시리얼을 택한다.

  3. 두 종류의 시리얼이 모두 선택지에 없다면, 실망스러운 목소리로 음메~ 하고 운 다음, 아무것도 택하지 않는다.

1번부터 N번까지의 소들은 시리얼을 받기 위해 줄을 서 있다 (당연히 앞에 있는 소가 시리얼 선택을 먼저 한다.).

각 소들은 항상 자신이 맨 앞줄이라면…… 하는 상상을 하곤 한다. 

i+1번째 소의 행복한 상상을 시각적으로 보여주기 위해서, 모든 정수 0≤i≤N-1값에 있어서 앞에서부터 i마리의 소가 없어졌을 때 시리얼을 먹을 수 있는 소의 수를 출력하는 프로그램을 작성하라.​


입력

첫 줄에 정수 N과 M이 공백을 사이에 두고 주어진다(1≤N≤​100,000 , 1≤​M≤​100,000)​

 

다음 N줄에 걸쳐서, i번째 소가 가장 좋아하는 시리얼 번호인 f와 차선으로 좋아하는 시리얼 번호인 s가 공백을 사이에 두고 주어진다​. (1≤​f,s≤​M)


출력

0≤i≤N-1​인 i값에 있어서 앞에서부터 i마리의 소가 없어졌을 때 시리얼을 먹을 수 있는 소의 수를 순서대로 출력한다.


예제1

입력
42

12
12
12
12
출력
2

2
2
1

태그


출처

USACO 2020 US Open Silver

역링크 공식 문제집만