Description

There are $n$ students in the school, and their friendships satisfy the following conditions:

• If $a$ and $b$ are friends, then $b$ and $a$ are also friends.
• The students can be divided into groups. Each student belongs to exactly one group, and:
  • Each group has at least $1$ student and at most $p$ students.
  • In each group, there are at most $q$ pairs of friends such that one student is in this group and the other student is in a different group.

Two students in the same group do not necessarily have to be friends.
Now she asks you to determine whether these students are lying.
If they are not lying, she wants you to provide a valid grouping.

Input Format

The first line contains three integers $n, p, q$, representing the number of students, the size limit within a group, and the limit on friend pairs across different groups.
Students are numbered from $0$ to $n - 1$.
Then follow $n$ lines. Starting from student $0$, each line begins with an integer $m_i$, which is the number of friends of this student, followed by $m_i$ integers indicating who those friends are.

Output Format

If these students are lying, output detention and terminate.
If these students are not lying, first output home.
Then output an integer $G$, meaning the students can be divided into $G$ groups.
Next, output $G$ lines. Each line starts with an integer $G'$, the number of students in this group, followed by $G'$ integers $g_i$, the IDs of the students in this group.
Any valid output is accepted.

4 2 1
1 1
2 0 2
2 1 3
1 2

home
2
2 0 1
2 2 3

5 2 1
1 1
2 0 2
2 1 3
2 2 4
1 3

detention

3 3 3
2 1 2
2 0 2
1 0

detention

Hint

Constraints

This problem uses bundled tests.

• Subtask 1 (20 pts): $n \le 16$.
• Subtask 2 (37 pts): $n \le 250$, $q \le 2$.
• Subtask 3 (12 pts): $q \le 2$.
• Subtask 4 (31 pts): no special constraints.

For $100\%$ of the testdata, $1 \le n \le 2500$, $p + q \le 15$, $\sum m_i \le 30000$, and students are not friends with themselves.

This problem uses Special Judge.

Notes

Translated from BOI 2017 D2 T2 Friends.
Translator: @一只书虫仔.

spj message explanation:

• Accepted: the answer is correct.
• Wrong Answer[0]: wrong judgment.
• Wrong Answer[1]: the sizes of some groups do not meet the requirements.
• Wrong Answer[2]: some groups contain IDs not in $0$ to $n - 1$.
• Wrong Answer[3]: some people belong to multiple groups.
• Wrong Answer[4]: some people do not belong to any group.
• Wrong Answer[5]: the grouping does not meet the requirements.

spj author:

Translated by ChatGPT 5