Maximizing Office Buildings

Bytel, a mobile telephony potentate, has allocated company phones to its employees. Each phone stores the numbers of some of its co‐workers, and every employee's number is stored on all phones of those who know him. In view of the company’s dynamic growth, the board has decided to move to new office buildings. In order to boost work efficiency, every pair of employees working in different buildings must know each others’ phone number (i.e. each such pair must be connected by an edge).

Your task is to help plan the maximal number of office buildings as well as determine the size of each building such that the aforementioned condition is satisfied. In other words, you are to partition the set of employees into as many groups as possible under the following constraint: if two employees are assigned to different buildings then they must have each other’s phone number (i.e. there is an edge between them). Note that there is no requirement for employees working in the same building.

This situation can be modeled by an undirected graph with n vertices (employees) and edges representing mutual phone number exchanges. Observe that if two employees do not have an edge between them then, by the board’s rule, they must be allocated to the same building. Consequently, if we define an equivalence relation where two employees are related if there is no edge between them (or a chain of such non-edges exists), the connected components of the resulting complement graph yield the grouping.

The final answer consists of the number of buildings and a list of the sizes of each building in non-decreasing order.

The relation can be written in \LaTeX as: for any two employees u and v, if \( (u,v) \notin E \) then they must be in the same building. Equivalently, the partition corresponds to the connected components in the complement graph \( \overline{G} \), where an edge between \( u \) and \( v \) exists if and only if \( (u,v) \notin E \) for \( u \neq v \).

inputFormat

The input is given from the standard input and has the following format:

 n
 k1 a1 a2 ... ak1
 k2 b1 b2 ... bk2
 ...
 kn c1 c2 ... ckn

Here, the first line contains a single integer n (the number of employees). The following n lines describe the phone number lists of employees 1 through n. The i-th of these lines begins with an integer k_i (the number of phone numbers stored in employee i’s phone) followed by k_i space-separated integers. Each of these integers represents the number of another employee whose phone number is stored. It is guaranteed that if employee i has employee j’s number then employee j also has employee i’s number. Note that employees are numbered from 1 to n.

outputFormat

The output should be written to the standard output. The first line must contain a single integer m, the maximal number of office buildings (groups). The second line should contain m space-separated integers representing the sizes of these groups in non-decreasing order.

sample

3
2 2 3
2 1 3
2 1 2

3
1 1 1