Description

There are $n$ people numbered from $1$ to $n$, with some acquaintance relations among them. Your task is to divide these people into two groups such that:

• Everyone is assigned to one of the groups.
• Each group contains at least one person.
• In each group, every person knows every other member in the same group.

Subject to the above conditions, the absolute difference between the sizes of the two groups should be as small as possible. Please construct one feasible grouping.

Please note that $x$ knowing $y$ does not necessarily mean that $y$ knows $x$; $x$ knowing $y$ and $y$ knowing $z$ does not necessarily mean that $x$ knows $z$. That is, the acquaintance relation is directed and non-transitive.

Input Format

The first line contains an integer representing the total number of people $n$.

From line $2$ to line $(n + 1)$, each line contains several pairwise distinct integers ending with $0$. On line $(i + 1)$, the $j$-th integer $a_{i, j}$ (excluding $0$) indicates that person $i$ knows $a_{i, j}$.

Output Format

This problem uses a Special Judge.

If there is no solution, output a single line containing the string No solution.

If there is a solution, output two lines of integers describing the two groups. On each line, the first integer is the size of that group, followed by the member indices in ascending order, separated by spaces.

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

3 1 3 5
2 2 4

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

Hint

Constraints

For all test points, it is guaranteed that $2 \leq n \leq 100$, $1 \leq a_{i, j} \leq n$.

Explanation

SPJ provided by @zhouyonglong.

Translated by ChatGPT 5