luogu#P8371. [POI2001] 绿色游戏

[POI2001] 绿色游戏

题目描述

绿色游戏是一种两人游戏,双方分别称 Ann\text{Ann}Billy\text{Billy}。游戏的内容主要是轮流在棋盘上移动一颗棋子。

棋盘上的点一部分是绿色的,其余是白色的。它们全部从 11a+ba+b 编号。编号 11aa 的点属于 Ann\text{Ann} ,编号 a+1a+1a+ba+b 的点属于 Billy\text{Billy}。每个点都有一些后继点,均可一步到达。属于 Ann\text{Ann} 的点的后继点一定属于 Billy\text{Billy},反之亦然。所有的点都至少有一个后继点,这样总可以往下走一步。

游戏开始时把棋子放在任意的一点 PP 上,然后双方轮流移动棋子至当前所在点(属于移动方)的一个后继点上(属于对手)。游戏由点 PP 的拥有者开始,结束时棋子第二次到达了某一点,称点 QQ。如果在从点 QQ 至点 QQ 的一连串移动中,棋子至少一次被放到绿色点上,则 Ann\text{Ann} 赢。若从点 PP 开始,不管 Billy\text{Billy} 如何移动, Ann\text{Ann} 总能保证赢得这次游戏,则称 Ann\text{Ann} 对起始点 PP 有必胜的策略。

请你编写一个程序:

  1. 读入对棋盘的描述。

  2. 算出 Ann\text{Ann} 有必胜策略的起始点。

输入格式

首行有两个整数 aabb ,两个整数之间用一个空格分开,分别表示属于 Ann\text{Ann}Billy\text{Billy} 的点数 (1ab3000)(1 \le a,b \le 3000)。以下 a+ba+b 行是对各点的描述,先描述 Ann\text{Ann} 的点,再描述 Billy\text{Billy} 的点。

i+1i+1 行(1ia+b1 \le i \le a+b) 以整数 zkz,k 开始:zz 表示点 ii 的颜色(OO-白色,II-绿色),kk 表示后继点的数目。然后是 KK 个整数(2ka+b2 \le k \leq a+b),写在同一行,代表点 ii 后继点的编号,这些整数均用一个空格分开。绿点的个数不超过 100100 ,所有点的后继点的个数之和不超过 3000030000

输出格式

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

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