Król Bajtazar 正在为自己 $128$ 岁生日举办盛大宴会。他决定将受邀宾客安排在圆桌旁就坐,使得没有任何宾客独自坐在一张桌旁。他已经选好了 $n$ 位可能邀请的人,并将他们按重要性从高到低排序,依次编号为 $1$ 到 $n$(编号为 $1$ 的宾客最重要)。
宾客们要求很高:每个人都向国王提出了关于“谁可以坐在他右侧”的要求。国王希望每位受邀宾客都有合适的同伴,因此不会允许任何一位宾客的要求未被满足。所以可能无法邀请全部 $n$ 个人。Bajtazar 请你(宫廷信息学家)求出在所有可能的受邀集合中“最好的”那个,并给出一种将他们安排在若干圆桌旁的示例方案。国王被问到“最好”是什么意思时,作为一位 $127$ 岁的信息学外行,他却出人意料地给出了相当严谨的定义:
为了比较两组宾客集合,我选择编号最小且只属于其中一个集合的人。这个人所在的集合就是更好的集合。
在这样定义的顺序下,确实可以唯一确定所有可能宾客集合中哪一个是最好的。
输入格式
第一行包含一个整数 $n$($2 \le n \le 2000$),表示宾客人数。在接下来的 $n$ 行中,第 $i$ 行描述编号为 $i$ 的人的偏好。偏好描述以一个整数 $k_i$($k_i \ge 0$)开头,随后给出 $k_i$ 个两两不同的人员编号——这些是从 $1$ 到 $n$ 的整数,且不等于 $i$。每个这样的编号表示一位可以坐在编号为 $i$ 的人右侧的宾客。所有 $k_i$ 之和不超过 $5000$。
在价值 $50%$ 分数的测试中,额外满足条件:若人员 $a$ 允许人员 $b$ 坐在其右侧,则人员 $b$ 也允许人员 $a$ 坐在其右侧。特别地,这意味着这两个人可以一起坐在同一张两人桌旁。
在价值 $20%$ 分数的测试中,可以邀请全部 $n$ 位宾客参加宴会。
输出格式
输出第一行应包含一个整数 $s$,表示方案中的桌子数量。接下来的 $s$ 行应描述每张桌子。每张桌子的描述以一个整数 $g$ 开头,表示该桌就坐的宾客人数。随后给出 $g$ 个整数表示这些宾客的编号。宾客编号应按逆时针方向依次给出。第一个输出的宾客将坐在最后一个输出的宾客的右侧。
样例数据
对于输入数据:
6
3 2 6 3
0
1 4
1 1
1 4
1 5
一种正确输出为:
1
3 1 3 4
在上述样例中,邀请 1、3、4 号宾客比邀请 1、4、5、6 号宾客更好。根据国王的判定标准,决定更好集合的是编号为 3 的人。