队员分组

题目描述

有 $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。