1208. 分组问题

【问题描述】

你的任务是把一些人分成两组，使得：

·每个人都被分到其中一组；

·每个组都至少有一个人；

·一组中的每个人都认识其他同组成员；

·两组的成员人数尽量接近。

这个问题可能有多个解决方案，你只要输出任意一个即可，或者输出这样的分组法不存在。

【输入】

为了简单起见，所有的人都用一个整数标记，每个人号码不同，从1到N。

输入文件的第一行包括一个整数N（2≤N≤100），N就是需要分组的总人数；接下来的N行对应了这N个人，按每个人号码的升序排列，每一行给出了一串号码Aij（1≤Aij≤N，Aij≠i），代表了第i个人所认识的人的号码，号码之间用空格隔开，并以一个“0”结束。

【输出】

如果分组方法不存在，就输出信息“No solution”（输出时无需加引号）至输出文件；否则用两行输出分组方案；第一行先输出第一组的人数，然后给出第一组成员的号码，每个号码前有一个空格，同理给出第二组的信息。每组的成员号码顺序和组别顺序并不重要。

【样例】

teams.in                     teams.out

5                            3 1 3 5

2 3 5 0                      2 2 4

1 4 5 3 0

1 2 5 0

1 2 3 0

4 3 2 1 0