문제
농부 창호의 소들이 가장 좋아하는 아침식사 메뉴는 시리얼이다.
소들은 덩치가 크기 때문에, 한 끼에 시리얼 한 박스를 먹는다.
농부 창호의 목장에서는 최근 M박스의 시리얼을 받았다.
불행히도, M개의 시리얼은 모두 종류가 달랐다!
농부 창호의 N마리의 소들은 가장 좋아하는 시리얼과, 그 다음으로 좋아하는 시리얼이 있다.
소들에게 시리얼 선택지를 보여주면 다음과 같은 과정에 의해 시리얼을 선택한다.
자신이 가장 좋아하는 시리얼이 선택되지 않았다면, 그 시리얼을 택한다.
가장 좋아하는 시리얼을 이미 다른 소가 선택했고, 두 번째로 좋아하는 시리얼이 남아있다면, 그 시리얼을 택한다.
두 종류의 시리얼이 모두 선택지에 없다면, 실망스러운 목소리로 음메~ 하고 운 다음, 아무것도 택하지 않는다.
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
1 2
1 2
1 2
1 2
2
2
2
1