Problem D
Námsleið
Languages
en
is
The semester is coming to an end so it is time to plan your studies and choose courses for the next semester. Oh no! This list is so confusing! Each course has so many prerequisites! With such a chaotic layout, is it even possible to sign up for and complete all the courses in any number of semesters?
You may take as many courses as you wish each semester and you may finish your studies in as many semesters as you wish, but you should try to minimize the number of semesters. You may only sign up for courses for which you have finished all prerequisites. Since you are a stellar student, you pass all courses for which you sign up.
Input
The first line of input consists of one integer $n$, the number of courses. Then $n$ lines follow, the $i$-th of which describes the prerequisites of the $i$-th course. Each of the lines starts with a non-negative integer $m_ i$ which is followed by a space and a sequence of $m_ i$ distinct space separated integers $d_{i,1}, \dotsc , d_{i,m_ i}$, each between $1$ and $n$, denoting the courses which are prerequisites for course $i$.
Output
If it is impossible to finish all the courses, simply output one line with the text Omogulegt!. Otherwise, output a line with the text Mogulegt! followed by a line containing a positive integer $k$, the minimum number of semesters you need to finish the courses. Then output $k$ lines, each of which starting with a positive integer denoting the number of courses taken that semester, followed by the space separated list of integers denoting the courses themselves. Each course should be listed exactly once.
If there are multiple solutions, you may output any of them.
Scoring
In the table below, let
\[ m = \sum _{i=1}^{n} m_ i \].
|
Group |
Points |
Constraints |
|
1 |
20 |
$1 \leq n \leq 50$, suffices to determine whether an ordering exists |
|
2 |
20 |
$1 \leq n \leq 50$, suffices to provide an ordering only when one exists, minimal ordering is not necessarry |
|
3 |
10 |
$1 \leq n \leq 50$ |
|
4 |
20 |
$1 \leq n, m \leq 200\, 000$, suffices to determine whether an ordering exists |
|
5 |
20 |
$1 \leq n, m \leq 200\, 000$, suffices to provide an ordering when one exists, minimal ordering is not necessary |
|
6 |
10 |
$1 \leq n, m \leq 200\, 000$ |
| Sample Input 1 | Sample Output 1 |
|---|---|
1 1 1 |
Omogulegt! |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 0 0 2 1 2 |
Mogulegt! 2 2 1 2 1 3 |
| Sample Input 3 | Sample Output 3 |
|---|---|
3 1 3 1 1 1 2 |
Omogulegt! |
| Sample Input 4 | Sample Output 4 |
|---|---|
12 0 0 0 0 1 1 1 3 1 1 1 1 0 0 1 5 2 1 4 |
Mogulegt! 3 4 3 4 1 2 4 8 7 6 5 4 9 10 11 12 |
