Baltic Olympiad in Informatics: 2017 Day 2, Problem 1

High school is all about being in the coolest group of friends. Headmistress Umbridge knows this, and she also knows that knowledge is power. She has collected data on all of the $n$ students at the school, asking each of them who they are friends with. Now she has a list of responses, but she is suspicious that some of the students might not have been entirely truthful during the questioning.

From anonymous (but highly reliable) sources, Headmistress Umbridge knows that the friendships at her school satisfy the following properties:

• If $a$ is friends with $b$ then $b$ is also friends with $a$.
• The set of students can be partitioned into groups, such that every student participates in exactly one group, where
  • each group has at least one and at most $p$ students, and
  • for each group there are at most $q$ pairs of friends with the first one in the group, and the second one outside of it.

Note that two students in the same group do not have to be friends.

Umbridge has hired you to figure out whether it is possible that all students are telling the truth, or whether she can be sure that at least one student is lying, and that she therefore should put everyone in detention. Is this morally questionable? Probably.

(In case the students may be telling the truth, you are worried that her suspicion might fall on you instead; thus you will also want to provide evidence of a valid partition if there is one.)

Input Specification

First a single line with three non-negative integers $n$, $p$ and $q$ as described above. Next follow $n$ lines, one for each student, starting with student $i=0$. Each such line starts with an integer $m_i$, denoting the number of friends student number $i$ claims that she has. Then follow $m_i$ distinct integers between $0$ and $n-1$, indicating who those friends are (the students are numbered from $0$ to $n-1$).

Constraints

We always have $1\le n\le 2500$, and $p+q\le 15$. Furthermore, it is guaranteed that $m_0+m_1+\cdots +m_{n-1}\le 30000$. A student never lists herself as one of her friends. For subcases, the inputs have these further restrictions:

• Group 1: 20 points $n\le 16$
• Group 2: 37 points $n\le 250$ and $q\le 2$
• Group 3: 12 points $q\le 2$
• Group 4: 31 points No further restrictions.

Output Specification

If Dolores can be certain someone didn't tell the truth, output detention. Otherwise, output home. If you output home on the first line, then you should prove your claim by outputting a partition of the students into groups such that the requirements above hold (if there are several, any one will do): The second line should then contain a positive integer $G$, the number of groups. The following $G$ lines should each begin with a positive integer $g_i$, the number of students in the $i$th group. Then on the same line, $g_i$ integers indicating the students in this group.

Sample Input 1

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

Sample Output 1

home
2
2 0 1
2 2 3

Sample Input 2

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

Sample Output 2

detention

Sample Input 3

3 3 3
2 1 2
2 0 2
1 0

Sample Output 3

detention