ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

1128. Partition into Groups

Time limit: 0.5 second
Memory limit: 64 MB
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
1 6
2 4 8
3 1 2 3
1 6
1 2 5 6
Problem Author: Dmitry Filimonenkov
Problem Source: VI Ural State University Collegiate Programming Contest (21.10.2001)