History of OI -> VIII OI 2000/2001 -> Problems

 News About Olympic History of OI XVII OI 2009/2010 XVI OI 2008/2009 XV OI 2007/2008 XIV OI 2006/2007 XIII OI 2005/2006 XII OI 2004/2005 XI OI 2003/2004 X OI 2002/2003 IX OI 2001/2002 VIII OI 2000/2001 Stage III - results Stage II - results Stage I - results Problems Regulations Organization Hints Schedule Stats VII OI 1999/2000 VI OI 1998/1999 V OI 1997/1998 IV OI 1996/1997 III OI 1995/1996 II OI 1994/1995 I OI 1993/1994 OI books National team Olympic camps Photo gallery Links SIO MAIN
 VIII Olimpiada Informatyczna 2000/2001

 Task: GRA Author: Marcin Jurdziński
Green game

 I stage contest

"Green game" is a game for two players, say Ann and Billy. Their task is to shift a pawn on the board.
Some fields of the board are green, the rest is white. All of them are numbered by integers from the interval 1...(a+b). The fields with integers from the interval 1...a belong to Ann, the fields with numbers (a+1)...(a+b) to Billy.
For each field there is given a set of successors, containing the fields one can get to from this field in one move. These sets were chosen in such a way that from the field belonging to Ann one can get in one move to the Billy's fields only, and vice versa. All the fields have non-empty sets of successors, thus one can always make a move.

At the beginning of the game we put a pawn on the arbitrarily chosen start field P, then players shift the pawn by turns from their field to any successor of this field (we know it belongs to the opponent). The game is started by an owner of the start field P. The game is finished when the pawn stays for the second time on the same field, say the field Q. If in the sequence of moves from the field Q to the field Q taken for the second time, the pawn was put at least once on the green field, Ann wins the game, otherwise Billy wins. We say that Ann has a winning strategy for the given start field P in case when there is such a method, which guarantees that she wins the game beginning from this field, no matter what moves Billy makes.

Task

Write a program which:

• reads from the text file GRA.IN the description of the board,
• computes the set of fields for which Ann has a winning strategy,
• writes the result in the text file GRA.OUT.

Input

In the first line of the text file GRA.IN there are written two positive integers a, b, separated by a single space, meaning respectively: the number of fields belonging to Ann, the number of fields belonging to Billy. Integers a, b satisfy the condition: 1 <= a+b <= 3000. In the following a+b lines there are descriptions of the fields of the board: first, descriptions of fields belonging to Ann, and then, of ones belonging to Billy. The (i+1)-st line, for 1 <= i <= a+b, begins with integers z, k meaning respectively the colour of the field i (0 means white, 1 - green) and the number of successors of this field. Then k integers (1 <= k < a+b) are written (still in the same line). They are the numbers denoting the successors of the i-th field. The integers in each line are separated by single spaces. The number of green fields on the board is not greater than 100. The total number of successors of all the fields on the board is not grater than 30000.

Output

The first line of the text file GRA.OUT should contain exactly one integer l, which indicates the number of fields for which Ann has a winning strategy. The following l lines should contain numbers of these fields written in ascending order - each integer should be written in a separate line.

Example

For the input file GRA.IN:

```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
```

the correct answer is the output file GRA.OUT:

```5
1
2
4
6
7```

Print friendly version