P1285 Team Grouping

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.

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}$.

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.

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