USACO 2020 Open Contest Silver #2(Credit: Dhruv Rohatgi)- 시리얼 > 문제은행 : 정보올림피아드&알고리즘




3703 : 시리얼

제한시간
1000 ms   
메모리제한
256 MB   
해결횟수
11 회   
시도횟수
24 회   

문제

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

 

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

 

농부 창호의 목장에서는 최근 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마리의 소가 없어졌을 때 시리얼을 먹을 수 있는 소의 수를 순서대로 출력한다.


입력 예

4 2
1 2
1 2
1 2
1 2

출력 예

2
2
2
1


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP