luogu#P6126. [JSOI2012] 始祖鸟

[JSOI2012] 始祖鸟

题目描述

最近,进香河地带出现了一家“始祖鸟专卖店”,然而这并不只是一时的心血来潮。

早在远古时期,进香河地带就以其秀美的环境和适宜的温度吸引了成群的始祖鸟。始祖鸟是一种团结的鸟类,它们总是通过各种方式来增强种群内部的交流,聚会则是其中之一。因为聚会不但可以增强朋友之间的友谊,而且可以认识新的朋友。

现在有 NN 只始祖鸟,我们从 11 开始编号。对于第 ii 只始祖鸟,有 MiM_i 个认识的朋友,它们的编号分别是 Fi,1Fi,2Fi,MiF_{i,1},F_{i,2},…,F_{i,M_i}。朋友的认识关系是单向的,也就是说如果第ss只始祖鸟认识第 tt 只始祖鸟,那么第 tt 只始祖鸟不一定认识第 ss 只始祖鸟。

聚会的地点分为两处,一处在上游,一处在下游。对于每一处聚会场所,都必须满足对于在这个聚会场所中的始祖鸟,有恰好有偶数个自己认识的朋友与之在同一个聚会场所中。当然,每一只始祖鸟都必须在两处聚会场所之一。

现在需要你给出一种安排方式。你只需要给出在上游的始祖鸟编号,如果有多组解,请输出任何一组解。

输入格式

输入数据包含 N+1N+1 行,第一行是数字 NN,代表始祖鸟的个数。
接下来 NN 行,第 i+1i+1 行的第一个数字是 MiM_i,表示第 ii 只鸟的朋友个数。之后有 MiM_i 个数字依次为 Fi,1,Fi,2,,Fi,MiF_{i,1},F_{i,2},…,F_{i,M_i} 表示第ii只始祖鸟朋友的标号。

输出格式

输出数据包含 22 行,第一行有一个非负整数 kk,表示在上游参加聚会的始祖鸟个数。第二行有 kk 个正整数,表示在这个 kk 只始祖鸟的编号,你可以以任意顺序输出这些编号。如果无法满足要求,只输出一行Impossible

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

提示

数据规模与约定

  • 对于100%100\%的数据,1N20001 \le N \le 2000