P8371 [POI 2001 R1] Green Game

Green Game is a two-player game. The two players are called $\text{Ann}$ and $\text{Billy}$. The game consists of moving a single token on a board in turns. Some points on the board are green, and the rest are white. All points are numbered from $1$ to $a+b$. Points numbered $1$ to $a$ belong to $\text{Ann}$, and points numbered $a+1$ to $a+b$ belong to $\text{Billy}$. Each point has some successor points that can be reached in one move. The successors of a point belonging to $\text{Ann}$ must belong to $\text{Billy}$, and vice versa. Every point has at least one successor point, so it is always possible to move one step forward. At the start of the game, the token is placed on an arbitrary point $P$. Then the players alternately move the token from the current point (which belongs to the player whose turn it is) to one of its successor points (which belongs to the opponent). The owner of point $P$ moves first. The game ends when the token reaches some point for the second time; call this point $Q$. If, during the sequence of moves from point $Q$ back to point $Q$, the token is placed on a green point at least once, then $\text{Ann}$ wins. If, starting from point $P$, no matter how $\text{Billy}$ moves, $\text{Ann}$ can always guarantee winning the game, then we say that $\text{Ann}$ has a winning strategy for the starting point $P$. Write a program to: 1. Read the description of the board. 2. Determine all starting points for which $\text{Ann}$ has a winning strategy.

The first line contains two integers $a$ and $b$, separated by a single space, representing the numbers of points belonging to $\text{Ann}$ and $\text{Billy}$, respectively $(1 \le a, b \le 3000)$. The next $a+b$ lines describe the points, first all of $\text{Ann}$'s points, then all of $\text{Billy}$'s points. Line $i+1$ $(1 \le i \le a+b)$ starts with integers $z, k$: $z$ denotes the color of point $i$ ($0$ for white, $1$ for green), and $k$ denotes the number of successor points. Then follow $k$ integers on the same line, giving the indices of the successor points, separated by single spaces. The number of green points does not exceed $100$, and the sum of the numbers of successor points over all points does not exceed $30000$.

The first line contains a single integer $L$, the number of starting points for which $\text{Ann}$ has a winning strategy. The next $L$ lines list these point indices in increasing order, one per line.

Translated by ChatGPT 5