Cuộc sống trung học xoay quanh việc được ở trong nhóm bạn sành điệu nhất. Hiệu trưởng Umbridge biết điều này, và bà cũng biết rằng thông tin là sức mạnh. Bà đã thu thập dữ liệu về toàn bộ \(n\) học sinh trong trường bằng cách hỏi từng người xem ai là bạn của họ. Giờ đây, bà có một danh sách các câu trả lời, nhưng lại nghi ngờ rằng một số học sinh có thể đã không hoàn toàn trung thực khi được hỏi.
Từ những nguồn tin giấu tên nhưng rất đáng tin cậy, Hiệu trưởng Umbridge biết rằng các mối quan hệ bạn bè trong trường thỏa mãn những tính chất sau:
- Nếu \(a\) là bạn của \(b\) thì \(b\) cũng là bạn của \(a\).
- Có thể chia toàn bộ học sinh thành các nhóm sao cho mỗi học sinh thuộc đúng một nhóm. Mỗi nhóm có ít nhất một và nhiều nhất \(p\) học sinh. Với mỗi nhóm, có nhiều nhất \(q\) cặp bạn bè mà một người thuộc nhóm và người còn lại ở ngoài nhóm.
Hai học sinh trong cùng một nhóm không nhất thiết phải là bạn của nhau.
Umbridge thuê bạn xác định liệu có khả năng tất cả học sinh đều nói thật hay bà có thể chắc chắn rằng ít nhất một học sinh đang nói dối, và vì thế nên phạt tất cả học sinh ở lại trường. Điều đó có đáng ngờ về mặt đạo đức không? Có lẽ là có.
Nếu các học sinh có thể đều nói thật, bạn lo rằng bà sẽ quay sang nghi ngờ bạn; vì vậy, bạn còn cần đưa ra một cách chia nhóm hợp lệ để làm bằng chứng, nếu cách chia như vậy tồn tại.
Ảnh: Dolores Umbridge, Julio Oliveiraa, qua Flickr; CC BY-NC-SA 2.0.
Dữ liệu vào
Dòng đầu tiên chứa ba số nguyên không âm \(n\), \(p\) và \(q\) như được mô tả ở trên.
Tiếp theo là \(n\) dòng, lần lượt ứng với các học sinh \(i=0,1,\ldots,n-1\). Mỗi dòng bắt đầu bằng số nguyên \(m_i\), là số người bạn mà học sinh \(i\) khai rằng mình có. Sau đó là \(m_i\) số nguyên phân biệt từ \(0\) đến \(n-1\), cho biết những người bạn đó. Các học sinh được đánh số từ \(0\) đến \(n-1\).
Dữ liệu ra
Nếu Dolores có thể chắc chắn rằng có người không nói thật, in ra detention. Ngược lại, in ra home.
Nếu dòng đầu tiên là home, bạn phải chứng minh bằng cách in ra một cách chia học sinh thành các nhóm thỏa mãn những yêu cầu ở trên. Nếu có nhiều cách chia, bạn có thể in ra bất kỳ cách nào. Khi đó, dòng thứ hai chứa một số nguyên dương \(G\), là số nhóm. Mỗi dòng trong \(G\) dòng tiếp theo bắt đầu bằng số nguyên dương \(g_i\), là số học sinh trong nhóm thứ \(i\), theo sau trên cùng dòng bởi \(g_i\) số nguyên chỉ các học sinh thuộc nhóm này.
Ràng buộc
- \(1 \le n \le 2\,500\).
- \(p,q \ge 0\) và \(p+q \le 15\).
- \(m_0+m_1+\cdots+m_{n-1} \le 30\,000\).
- Danh sách của mỗi học sinh gồm các số hiệu phân biệt trong đoạn từ \(0\) đến \(n-1\).
- Không học sinh nào liệt kê chính mình trong danh sách bạn bè.
Phân nhóm
Bạn chỉ nhận được điểm của một nhóm khi vượt qua tất cả các test trong nhóm đó. Tổng điểm là tổng điểm của các nhóm.
- Nhóm 1 (20 điểm): \(n \le 16\).
- Nhóm 2 (37 điểm): \(n \le 250\) và \(q \le 2\).
- Nhóm 3 (12 điểm): \(q \le 2\).
- Nhóm 4 (31 điểm): Không có ràng buộc bổ sung.
Ví dụ
Ví dụ 1
Input
4 2 1
1 1
2 0 2
2 1 3
1 2
Output
home
2
2 0 1
2 2 3
Ví dụ 2
Input
5 2 1
1 1
2 0 2
2 1 3
2 2 4
1 3
Output
detention
Ví dụ 3
Input
3 3 3
2 1 2
2 0 2
1 0
Output
detention
Nguồn
Baltic Olympiad in Informatics 2017, ngày thi thứ 2.
