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




3703 : 시리얼

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

문제

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

 

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

 

농부 창호의 목장에서는 최근 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