logo AlgoBeat OnlineJudge
登录 注册

#200282. [NEERC 2001] 队员分组

内存限制:125 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

个人从 编号,相互之间有一些认识关系,你的任务是把这些人分成两组,使得:

  • 每个人都被分到其中一组。
  • 每个组都至少有一个人。
  • 一组中的每个人都认识其他同组成员。

在满足上述条件的基础上,要求两组成员的人数之差(绝对值)尽可能小。请构造一种可行的方案。

请注意, 认识 不一定说明 认识 认识 认识 不一定说明 认识 。即认识关系是单向且不可传递的。

输入格式

输入的第一行是一个整数,代表总人数

到第 行,每行有若干个互不相同的整数,以 结尾,第 行的第 个整数 除外)代表第 个人认识

输出格式

本题存在 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

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

样例输出 2

No solution

数据范围与提示

数据规模与约定

对于全部的测试点,保证

说明

由 @zhouyonglong 提供 SPJ。