문제
헤드미스트리스 엄브릿지는 학교의 학생들 사이의 우정 관계를 조사했다. 모든 학생들에게 자신이 친구라고 주장하는 사람들의 목록을 요청했지만, 일부 학생들이 거짓말을 했을 가능성을 의심하고 있다.
엄브릿지는 익명의 (그러나 매우 신뢰할 수 있는) 소스에서 아래와 같은 학교의 우정 관계 조건을 알고 있다:
대칭적 우정: 만약 학생 a가 b와 친구라면, b도 a와 친구이다.
그룹 분할: 학생들을 그룹으로 나눌 수 있으며, 이 그룹들은 다음 조건을 만족한다:
각 그룹에는 최소 1명, 최대 p명의 학생이 있어야 한다.
각 그룹에서 그룹 내 학생이 그룹 외부의 학생과 친구인 경우는 최대 q쌍 이하이다.
엄브릿지는 이 조건을 만족할 수 없는 경우, 적어도 한 학생이 거짓말을 했다고 확신할 수 있으며 모든 학생을 detention(벌)으로 보낼 것이다. 반면, 조건을 만족하는 그룹 분할이 가능하다면 home(집)으로 돌려보낼 것이다.
입력
첫 번째 줄: 세 개의 정수 n, p, q (학생 수, 그룹 내 최대 학생 수, 그룹 외부와의 최대 친구 수)
다음 n개의 줄: 각 줄은 아래를 포함한다:
정수 mᵢ: i번 학생이 친구라고 주장하는 학생 수
mᵢ개의 정수: 친구라고 주장하는 학생들의 번호 (중복 없음)
출력
조건을 만족할 수 없다면,
"detention"을 출력한다.조건을 만족할 수 있다면:
첫 줄에
"home"을 출력한다.두 번째 줄에 그룹의 수 G를 출력한다.
이후 G개의 줄에 각 그룹의 정보를 출력한다:
첫 번째 정수는 그룹의 학생 수 gᵢ.
그 뒤에 그룹에 속한 학생들의 번호 gᵢ개.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 20점 | |
| #2 | 37점 | |
| #3 | 12점 | |
| #4 | 31점 | 추가 제약 조건 없음 |
예제1
421
11
202
213
12
home
2
201
223
예제2
521
11
202
213
224
13
detention
예제3
333
212
202
10
detention