#P3429. [POI2005] DWA-Two Parties

[POI2005] DWA-Two Parties

题目描述

拜占庭国王要举办两个大派对,并且希望邀请更多的居民。

国王从他的丰富经验里知道,如果一个居民在派对上能遇到偶数个的朋友,那他会非常高兴。因此,他要求你邀请国家的居民去两个派对,而使尽可能多的人在他们的聚会上有偶数个的朋友。

认识是一种对称关系,如 AA 认识 BB,那么 BB 也认识 AA

输入格式

N+1N+1 行。

第一行读入一个整数 NN1N2001\le N\le 200),表示居民的数量。

接下来 NN 行,第 i+1i+1 行是一个整数 lil_i,表示第 ii 个居民的朋友数量,接着是 lil_i 个数,为第 ii 个居民的朋友编号。我们假设没有人是自己的朋友。如果 BB 出现在了 AA 的朋友列表中,那么 AA 也会出现在BB 的列表中。

输出格式

第一行是一个整数 MM,是前往第一个排队的人数。第二行 MM 个整数,是去第一个派对的居民编号,其余的居民前往第二个派对。

如果有多种答案,你只需要输出一个。

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