Description

Xiao Z cannot stand loneliness and plans to host a DOTA tournament. To let the entire ACM class participate, he also made a custom DOTA map that can support any number of players versus any number.

Now here comes the problem: how to split so many people into two teams? Xiao Z's idea is that everyone reports the classmates they are willing to be on the same team with, and then Xiao Z will divide everyone into two teams under the following requirement:

For any student A, everyone who is on the same team as A must all be classmates that A is willing to be on the same team with.

Xiao Z wants the difference in team sizes to be as small as possible. If such a grouping does not exist, output No solution.

Input Format

The first line contains $N$, the total number of students.

Then lines $2$ through $N+1$, each line lists the classmates this student is willing to be on the same team with, ending with $0$.

Output Format

One line. If a solution exists, output the sizes of the two teams, with the smaller size first; otherwise, output No solution.

5
3 4 5 0
1 3 5 0
2 1 4 5 0
2 3 5 0
1 2 3 4 0

No solution

5
2 3 5 0
1 4 5 3 0
1 2 5 0
1 2 3 0
4 3 2 1 0

2 3

Hint

For $30\%$ of the testdata, $N \leq 10$;

For $100\%$ of the testdata, $N \leq 2000$.

Translated by ChatGPT 5