Problem E
Námsleið

Önnin er að klárast og núna þarftu að plana námið þitt og velja áfanga fyrir næstu önn. Æ nei! Þessi listi er svo ruglandi! Hver einasti áfangi er með svo marga undanfara! Fyrst skipulagið er í svona mikilli ringulreið er einu sinni mögulegt að skrá sig í og klára alla áfanga í einhverjum fjölda anna?

Þú mátt taka eins marga áfanga og þú vilt á hverri önn og þú mátt klára námið á eins mörgum önnum og þú vilt, en þú ættir að reyna að lágmarka fjölda anna. Þú mátt einungis skrá þig í áfanga ef þú hefur klárað alla undanfara áfangans. Þar sem þú ert stjörnunemandi nærðu öllum áföngum.

Inntak

Fyrsta lína inntaksins inniheldur eina heiltölur $n$, fjölda áfanga. Næst fylgja $n$ línur þar sem $i$-ta línan lýsir undanförum $i$-ta áfangans. Hver þessarra lína byrjar á heiltölu $m_i$ og næst kemur bil og runa af $m_i$ ólíkum heiltölum aðskildar af bilum, $d_{i,1},\dots ,d_{i,m_i}$, sérhver þeirra á bilinu $1$ upp í $n$, sem tákna þá áfanga sem eru undanfarar fyrir $i$-ta áfangann.

Úttak

Ef það er ómögulegt að klára alla áfangana skaltu einfaldlega skrifa út eina línu með textanum "Omogulegt!". Annars skaltu skrifa út línu með textanum "Mogulegt!" og aðra línu með jákvæðri heiltölu $k$, sem táknar minnsta fjölda anna sem þú þarft til að klára alla áfangana. Næst skaltu skrifa út $k$ línur, hver þeirra skal byrja á jákvæðri heiltölu sem táknar fjölda áfanga sem eru teknir á þeirri önn og á eftir henni skal koma runa af heiltölum aðskildar af bilum sem tákna áfangana sjálfa. Hver áfangi skal koma fram nákvæmlega einu sinni í úttakinu.

Ef til eru margar lausnir máttu skrifa út einhverja þeirra.

Stigagjöf

Í töflunni að neðan látum við

.

1
1 1

Omogulegt!

3
0
0
2 1 2

Mogulegt!
2
2 1 2
1 3

3
1 3
1 1
1 2

Omogulegt!

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