There are N children in the kindergarten. Unfortunately, the children quarrel though not often. Each child has not more than three adversaries. Is it possible to partition the children into two groups (possibly not equal), so that each child would have not more than one adversary in his or her group?
The first line contains an integer N, 0 < N ≤ 7163. The next N lines contain lists of adversaries of each child. A line starts with the amount of the corresponding child's adversaries, then the numbers of the adversaries follow. The numbers in each line are separated with a space.
The first line contains the number of children in the smaller group. The next line contains the list of children in the group. The numbers in the second line are separated with a space. If the groups are of the same size then you are to describe the group that contains the child number one. Note that the output may contain the only number 0. If there
are several possible partitions it's sufficient to output an arbitrary one. If there's no possible partition you are to output the only string “NO SOLUTION”.
3 2 3 7
3 1 3 7
3 1 2 7
2 4 8
3 1 2 3
1 2 5 6
Problem Author: Dmitry Filimonenkov
Problem Source: VI Ural State University Collegiate Programming Contest (21.10.2001)