队员分组
题目描述
有 $n$ 个人从 $1$ 至 $n$ 编号,相互之间有一些认识关系,你的任务是把这些人分成两组,使得:
- 每个人都被分到其中一组。
- 每个组都至少有一个人。
- 一组中的每个人都认识其他同组成员。
在满足上述条件的基础上,要求两组成员的人数之差(绝对值)尽可能小。请构造一种可行的方案。
请注意,$x$ 认识 $y$ 不一定说明 $y$ 认识 $x$;$x$ 认识 $y$ 且 $y$ 认识 $z$ 不一定说明 $x$ 认识 $z$。即认识关系是单向且不可传递的。
输入输出格式
输入格式
输入的第一行是一个整数,代表总人数 $n$。
第 $2$ 到第 $(n + 1)$ 行,每行有若干个互不相同的整数,以 $0$ 结尾,第 $(i + 1)$ 行的第 $j$ 个整数 $a_{i, j}$($0$ 除外)代表第 $i$ 个人认识 $a_{i, j}$。
输出格式
**本题存在 Special Judge**。
如果无解,请输出一行一个字符串 `No solution`。
如果有解,请输出两行整数,分别代表两组的成员。每行的第一个整数是该组的人数,后面**以升序**若干个整数代表该组的成员编号,数字间用空格隔开。
输入输出样例
输入样例 #1
5
2 3 5 0
1 4 5 3 0
1 2 5 0
1 2 3 0
4 3 2 1 0
输出样例 #1
3 1 3 5
2 2 4
说明
#### 数据规模与约定
对于全部的测试点,保证 $2 \leq n \leq 100$,$1 \leq a_{i, j} \leq n$。
#### 说明
由 @zhouyonglong 提供 SPJ。