RiseOJ – 시리얼

설명

농부 존(Farmer John)의 소들은 아침 식사로 시리얼을 무엇보다 좋아한다! 실제로 소들은 식성이 엄청나서, 한 끼에 시리얼 한 상자를 통째로 먹어 치운다.

농장에 최근 $$M$$ 가지 종류의 시리얼 $(1\le M\le 10^5)$ 이 배송되었다. 안타깝게도 각 시리얼은 한 상자씩밖에 없다! $$N$$ 마리의 소 $(1\le N\le 10^5)$ 에게는 각각 가장 좋아하는 시리얼과 두 번째로 좋아하는 시리얼이 있다. 고를 수 있는 시리얼들이 주어지면, 소는 다음 과정을 수행한다.

가장 좋아하는 시리얼 상자가 아직 남아 있으면, 그것을 가지고 떠난다.
그렇지 않고 두 번째로 좋아하는 시리얼 상자가 남아 있으면, 그것을 가지고 떠난다.
그렇지 않으면, 실망하여 음머 하고 울고는 아무 시리얼도 가지지 않고 떠난다.

소들이 시리얼을 받기 위해 한 줄로 서 있다. 각 $0 \leq i \leq N-1$ 에 대해, 농부 존이 줄의 앞에서 $$i$$ 마리의 소를 제외시켰을 때 시리얼 상자를 가져가는 소가 몇 마리인지 구하시오.

문제 제공: Dhruv Rohatgi

제약

배점

테스트 케이스 2-3은 $N,M\le 1000.$ 을 만족한다.
테스트 케이스 4-10은 추가 제약이 없다.

문제 제공: Dhruv Rohatgi

입력 형식

첫째 줄에 공백으로 구분된 두 정수 $$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.$$ 에 대한 답을 한 줄에 하나씩 출력한다.

Standard input / output

This problem is judged over standard input/output. The original contest used named files — if you prefer the classic interface, tick “File I/O” on the submit form and read/write these files instead:

입력을 읽을 파일 cereal.in · 출력을 쓸 파일 cereal.out

예제 1

입력

출력

설명

If at least two cows remain, then exactly two of them get a box of cereal.

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2019-2020 > US Open > Silver

올림피아드 > USACO > 2019-2020 > US Open > Silver

태그

JudgeUSACO

시리얼

평가 및 의견

풀이 제출