BZPRO

#2948. [Poi2001]绿色游戏

内存限制：128 MiB 时间限制：1 Sec
提交 提交记录 讨论

题目描述

绿色游戏是一种两人游戏，双方分别称Ann和Billy。游戏的内容主要是轮流在棋盘上移动一颗棋子。
棋盘上的点一部分是绿色的，其余是白色的；全部从1至a+b编号。编号1至a的点属于Ann，编号(a+1)至(a+b)的点属于Billy。每个点都有一些后继点，均可一步到达。属于Ann的点的后继点一定属于Billy，反之亦然。所有的点都至少有一个后继点，这样总可以往下走一步。
游戏开始时把棋子放在任意的一点P上，然后双方轮流移动棋子至当前所在点（属于移动方）的一个后继点上（属于对手）。游戏由点P的拥有者开始，结束时棋子第二次到达了某一点，称点Q。如果在从点Q至点Q的一连串移动中，棋子至少一次被放到绿色点上，则Ann赢。若从点P开始，不管Billy如何移动，Ann总能保证赢得这次游戏，则称Ann对起始点P有必胜的策略。
任务：
       编写一个程序，完成下列工作：
1、 读入对棋盘的描述；
2、 算出Ann有必胜策略的起始点；

输入格式

首行有两个整数a和b，两个整数之间用一个空格分开，分别表示属于Ann和Billy的点数(1≤a，b≤3000)。以下a+b行是对各点的描述，先描述Ann的点，再描述Billy的点。第i+1行（1≤i≤a+b）以整数z，k开始：z表示点i的颜色(O－白色，I－绿色)，k表示后继点的数目。然后是K个整数（1≤k＜a+b），写在同一行，代表点i后继点的编号，这些整数均用一个空格分开。绿点的个数不超过100，所有点的后继点的个数之和不超过30000。

输出格式

首行仅一个整数L，代表Ann有L个有必胜策略的起始点。以下L行按升序顺序依次给出这些点的编号。

样例

样例输入


			
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

数据范围与提示

BZPRO Powered by Remmina.
Github Repository