bzoj#P2948. [Poi2001]绿色游戏
[Poi2001]绿色游戏
题目描述
绿色游戏是一种两人游戏,双方分别称 Ann 和 Billy。游戏的内容主要是轮流在棋盘上移动一颗棋子。
棋盘上的点一部分是绿色的,其余是白色的;全部从 至 编号。编号 至 的点属于 Ann,编号 至 的点属于 Billy。每个点都有一些后继点,均可一步到达。属于 Ann 的点的后继点一定属于 Billy,反之亦然。所有的点都至少有一个后继点,这样总可以往下走一步。
游戏开始时把棋子放在任意的一点 上,然后双方轮流移动棋子至当前所在点(属于移动方)的一个后继点上(属于对手)。游戏由点 的拥有者开始,结束时棋子第二次到达了某一点,称点 。如果在从点 至点 的一连串移动中,棋子至少一次被放到绿色点上,则 Ann 赢。若从点 开始,不管 Billy 如何移动,Ann 总能保证赢得这次游戏,则称 Ann 对起始点 有必胜的策略。
任务:
编写一个程序,完成下列工作:
- 读入对棋盘的描述;
- 算出 Ann 有必胜策略的起始点。
输入格式
首行有两个整数 和 ,两个整数之间用一个空格分开,分别表示属于 Ann 和 Billy 的点数。
以下 行是对各点的描述,先描述 Ann 的点,再描述 Billy 的点。第 行()以整数 开始: 表示点 的颜色(0
表示白色,1
表示绿色), 表示后继点的数目。然后是 个整数(),写在同一行,代表点 后继点的编号,这些整数均用一个空格分开。绿点的个数不超过 ,所有点的后继点的个数之和不超过 。
输出格式
首行仅一个整数 ,代表 Ann 有 个有必胜策略的起始点。以下 行按升序顺序依次给出这些点的编号。
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
数据规模与约定
对于 的数据,。