6948: BZOJ2948:[Poi2001]绿色游戏

Memory Limit:128 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

绿色游戏是一种两人游戏,双方分别称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

提示

没有写明提示


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: