1719. [POI 2001]绿色游戏

【题目描述】

“绿色游戏”是一个双人游戏，不妨把两名玩家称为安和比利。他们的需要在棋盘上移动卒子。

棋盘上的一些区域是绿色的，其他区域为白色。所有这些区域用从1到a+b的正整数编号。编号为1...a的区域属于安，编号为(a+1)...(a+b)的区域属于比利。

对每个区域都给定一个后继集合，包含棋子从这个区域可以一步移到的所有区域。这些集合的选取方式使得从属于安的区域只能移动到属于比利的区域，反之亦然。所有的区域都有非空的后继集合，因此棋子总有路可走。

在游戏开始时我们把一个卒子放在任意的初始位置P，然后玩家轮流移动棋子，将它移至当前所在格的某一后继（显然这个区域属于对手）。初始位置P的拥有者先移动。当棋子被移到某个先前停留过的位置，不妨叫Q时游戏结束。如果在棋子从Q到第二次停在Q的移动序列中，至少一次停留在绿色的区域，安就赢得了游戏，否则比利赢。我们说对于给定的起点P，安有必胜策略，当且仅当无论比利如何移动，她都能赢得从这个位置开始的游戏。

写一个程序：

·读入棋盘的描述

·计算安有必胜策略的起点集合

·输出结果

【输入格式】

第一行有两个正整数a,b，代表属于安的区域数和属于比利的区域数。1<=a+b<=3000.

接下来的a+b行每行描述了一个区域，首先是属于安的a个，然后是属于比利的b个。

对于1<=i<=a+b，第(i+1)行开头是两个整数z,k，代表区域i的颜色（0-白色，1-绿色），和其后继位置的数量。接下来是k个整数（1<=k<a+b），仍然在同一行，即区域i的所有后继。所有绿色区域的数量不超过100.所有位置后继集合大小的总和不超过30000.

【输出格式】

第一行一个整数I，代表安有必胜策略的位置数。

接下来I行从小到大输出所有安有必胜策略的位置。

【样例输入】

5 3

0 2 6 7

0 3 6 7 8

0 1 8

1 1 7

1 1 8

1 2 1 2

0 2 1 2

0 2 3 4

【样例输出】

5

1

2

4

6

7

【来源】

POI 2001 Green Game