点集偶划分
给定一个包含 个点的无向图,点的编号为 。请将所有点划分为两组,使得在每一组内部,每个点的同组邻居数量均为偶数,其中 也视为偶数。
根据 Gallai 定理,这样的划分一定存在,因此本题不存在无解的情况。你只需要输出其中一组。
输入格式
第一行包含一个整数 。
接下来 行,第 行的第一个整数 表示点 的邻居数量,随后 个整数依次给出这些邻居的编号。
图是无向图:若 出现在点 的邻居表中,则 也会出现在点 的邻居表中。
输出格式
第一行输出一个整数 ,表示所输出组中的点数。
第二行输出 个整数,表示该组中的所有点,点的顺序任意。当 时,该行为空行。
合法的划分通常不唯一,输出任意一组即可。同一个划分中的两组均为合法输出,因此允许 或 。
样例输入
3
1 2
2 1 3
1 2
样例输出
1
2
样例解释
样例中的图是一条由点 构成的链。将点集划分为 与 两组是合法的。
点 与点 的唯一邻居都是点 ,不在它们所在的组中,因此它们的同组邻居数量均为 。点 的两个邻居 也都不在点 所在的组中,因此点 的同组邻居数量同样为 。
样例输出给出的是其中一组,输出另一组同样正确。
数据范围
- 对于全部数据,;
- 邻居表的总长度不超过 ;
- 本题测试数据中,。
来源与许可
本题题面与测试数据整理自 BZOJ。
样例 1
输入
3
1 2
2 1 3
1 2
输出
1
2