P1026

点集偶划分

点集偶划分

给定一个包含 nn 个点的无向图,点的编号为 1,2,…,n1,2,\ldots,n。请将所有点划分为两组,使得在每一组内部,每个点的同组邻居数量均为偶数,其中 00 也视为偶数。

根据 Gallai 定理,这样的划分一定存在,因此本题不存在无解的情况。你只需要输出其中一组。

输入格式

第一行包含一个整数 nn。

接下来 nn 行,第 ii 行的第一个整数 kk 表示点 ii 的邻居数量,随后 kk 个整数依次给出这些邻居的编号。

图是无向图:若 jj 出现在点 ii 的邻居表中,则 ii 也会出现在点 jj 的邻居表中。

输出格式

第一行输出一个整数 mm,表示所输出组中的点数。

第二行输出 mm 个整数,表示该组中的所有点,点的顺序任意。当 m=0m=0 时,该行为空行。

合法的划分通常不唯一,输出任意一组即可。同一个划分中的两组均为合法输出,因此允许 m=0m=0 或 m=nm=n。

样例输入

3
1 2
2 1 3
1 2

样例输出

1
2

样例解释

样例中的图是一条由点 1,2,31,2,3 构成的链。将点集划分为 {1,3}\{1,3\} 与 {2}\{2\} 两组是合法的。

点 11 与点 33 的唯一邻居都是点 22,不在它们所在的组中,因此它们的同组邻居数量均为 00。点 22 的两个邻居 1,31,3 也都不在点 22 所在的组中,因此点 22 的同组邻居数量同样为 00。

样例输出给出的是其中一组,输出另一组同样正确。

数据范围

  • 对于全部数据,1≤n≤2001\le n\le 200;
  • 邻居表的总长度不超过 n(n−1)n(n-1);
  • 本题测试数据中,2≤n≤2002\le n\le 200。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

3
1 2
2 1 3
1 2

输出

1
2