원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)
간식 분배
원제: 간식 분배
문제
명의 학생과 개의 간식이 있다. 학생들과 간식에는 각각 의 번호가 붙어 있다.
각 학생은 개의 간식 중 하나 이상의 간식을 좋아한다. 보다 구체적으로, 번 학생은 개의 간식을 좋아하며, 그 간식들의 번호는 이다.
처음에 방 안에는 종류의 간식이 정확히 하나씩 놓여 있다. 다음과 같은 과정을 통해 학생들에게 간식을 분배하려고 한다.
- 명의 학생을 적절한 순서로 한 번에 한 명씩 방에 들여보낸다.
- 방에 들어간 학생은 현재 방에 남아있는 간식 중 자신이 좋아하는 모든 간식을 가져간다. 만약, 방 안에 자신이 좋아하는 간식이 하나도 없다면, 아무 간식도 가져가지 않는다.
명의 학생이 방에 들어가는 순서를 적절히 정하여, 모든 학생이 정확히 하나의 간식을 가져가도록 하는 것이 가능한지 판별하라. 만약 가능하다면, 그러한 순서를 아무거나 하나 구하라.
제약 조건
- 주어지는 모든 수는 정수이다.
- 정수 에 대하여
- 정수 와 정수 에 대하여
- 정수 에 대하여, 개의 정수 의 값은 모두 서로 다르다.
부분문제
- (6점) 정수 에 대하여
- (11점) 모든 학생이 정확히 하나의 간식을 가져가도록 하는 순서가 존재한다면, 의 번호 순서도 그러한 조건을 만족한다.
- (8점)
- (12점)
- (18점)
- (20점)
- (25점) 추가 제약 조건 없음.
입력 형식
첫 줄에 학생과 간식의 수를 나타내는 정수 이 주어진다.
그다음 개의 줄에 걸쳐, 명의 학생이 좋아하는 간식에 대한 정보가 주어진다. 이 중 번째 줄에는 정수 와 그 뒤에 개의 정수 가 공백으로 구분되어 차례대로 주어진다.
출력 형식
만약, 모든 학생이 정확히 하나의 간식을 가져가도록 하는 순서가 존재하지 않는다면, 첫 줄에 -1을 출력한다.
만약, 의 번호 순서대로 학생들이 방에 들어갈 때 모든 학생이 정확히 하나의 간식을 가져간다면, 첫 줄에 개의 정수 을 공백으로 구분하여 출력한다.
가능한 출력이 여러 개라면 그중 아무거나 하나를 출력해도 정답으로 인정된다.
예제
예제 1
3 2 1 2 2 2 3 1 2
3 1 2
각 학생이 좋아하는 간식은 다음과 같다.
- 번 학생은 번 간식을 좋아한다.
- 번 학생은 번 간식을 좋아한다.
- 번 학생은 번 간식을 좋아한다.
번, 번, 번 학생이 이 순서대로 방에 들어가면 각 학생은 정확히 하나의 간식을 가져간다.
- 처음에 방에는 번 간식이 모두 하나씩 있다.
- 번 학생이 방에 들어가면 번 간식을 가져간다. 이후 방에는 번 간식이 남아있다.
- 번 학생이 방에 들어가면 번 간식을 가져간다. 이후 방에는 번 간식이 남아있다.
- 번 학생이 방에 들어가면 번 간식을 가져간다.
마찬가지로, 번, 번, 번 학생이 이 순서대로 방에 들어가도 모든 학생은 정확히 하나의 간식을 가져간다.
예제 2
2 2 1 2 2 1 2
-1
두 학생 모두 모든 종류의 간식을 좋아하므로, 학생들이 어떤 순서로 방에 들어가더라도 처음으로 방에 들어간 학생이 모든 간식을 가져가게 된다.
예제 3
4 1 3 1 2 3 4 2 3 2 1 2
1 2 3 4