RiseOJ – 대규모 재파종

설명

긴 가뭄으로 농부 존의 $$N$$ 개 목초지에는 풀이 하나도 남지 않았다. 하지만 곧 우기가 다가오므로, 이제 "재파종"을 할 때가 되었다.

농부 존의 창고에는 네 개의 양동이가 있고, 각각에는 서로 다른 종류의 풀씨가 들어 있다. 존은 각 목초지에 이 씨앗들 중 한 종류를 뿌리고자 한다. 낙농업자인 농부 존은 자신의 소들이 다양한 식단을 즐길 수 있도록 하고 싶다. $$M$$ 마리의 소 각각에게는 가장 좋아하는 목초지가 두 곳 있는데, 존은 두 곳에 서로 다른 종류의 풀이 심어지도록 하여 모든 소가 두 종류의 풀 중에서 선택할 수 있게 하고 싶다. 농부 존은 어떤 목초지도 $$3$$ 마리보다 많은 소의 애호 목초지가 아니라는 것을 알고 있다.

모든 소의 영양적 요구가 충족되도록 각 목초지에 심을 풀 종류를 고르는 것을 도와주자.

문제 제공: Dhruv Rohatgi

제약

문제 제공: Dhruv Rohatgi

입력 형식

첫째 줄에 $$N$$ ( $2 \leq N \leq 100$ )과 $$M$$ ( $1 \leq M \leq 150$ )이 주어진다. 다음 $$M$$ 개의 줄 각각에는 $1 \ldots N$ 범위의 두 정수가 주어지는데, 이는 농부 존의 소 한 마리가 가장 좋아하는 두 목초지 쌍을 나타낸다.

출력 형식

각 자리가 $1 \ldots 4$ 범위인 $$N$$ 자리 수를 출력한다. 각 자리는 각 목초지에 심을 풀 종류를 나타내며, 첫째 자리는 목초지 $$1$$ , 둘째 자리는 목초지 $$2$$ 의 풀 종류에 대응하는 식이다. 유효한 답이 여러 개라면, 그중 가장 작은 $$N$$ 자리 수만 출력한다.

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:

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

예제 1

입력

출력

문제 정보

riseoj 작성

출처 올림피아드 > USACO > 2018-2019 > February > Bronze

올림피아드 > USACO > 2018-2019 > February > Bronze

태그

JudgeUSACO

대규모 재파종

평가 및 의견

풀이 제출