You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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

如果有解，请输出两行整数，分别代表两组的成员。每行的第一个整数是该组的人数，后面以升序若干个整数代表该组的成员编号，数字间用空格隔开。

5
2 3 5 0
1 4 5 3 0
1 2 5 0
1 2 3 0
4 3 2 1 0

3 1 3 5
2 2 4

提示

数据规模与约定

对于全部的测试点，保证 $2 \leq n \leq 100$，$1 \leq a_{i, j} \leq n$。

说明

由 @zhouyonglong 提供 SPJ。