Balanced Team Partition in DOTA Tournament

Little Z is tired of loneliness and is hosting a DOTA tournament. In order to include everyone from the ACM class, he has designed a special DOTA map that supports any number of players. Each player submits a list of other players they wish to be teamed up with. Little Z needs to partition all players into two teams under the following constraint:

• For any player A, every other player on A's team must be someone A is willing to team up with.

The goal is to minimize the difference in the number of players between the two teams. If no such partition exists, output No solution.

Note: Players are numbered from 1 to N.

inputFormat

The first line contains a single integer N representing the number of players.

Each of the following N lines describes one player's preferences. The i-th line begins with an integer m indicating the number of players that player i wishes to have in the same team, followed by m distinct integers (each between 1 and N, and not equal to i) representing those players.

outputFormat

If a valid partition exists, output two lines:

• The first line contains the player numbers (in increasing order) of the first team.
• The second line contains the player numbers (in increasing order) of the second team.

If multiple solutions exist, output any one that minimizes the team size difference. If no valid partition exists, print No solution.

sample

4
2 2 3
3 1 3 4
2 1 2
1 2

1 3
2 4