Wikipediaspråk

Om jag säger "Sortera orden [zebra, anka, duva]!" så svarar du snabbt [anka, duva, zebra]. Lätt, va? Det gäller även om du inte känner igen ordens innebörd eller alla tecken i språket, typ [fünf, como estás, désolé]. Vi kan ju svenska och engelska och vet att troligen är svaret [como estás, désolé, fünf]. Ännu inte så svårt. Men troligen finns det få programmeringsolympiaddeltagare som kan sortera sådana ordlistor så fort kinesiska, persiska och andra icke-latinska tecken är inblandade i ordlistorna. Hur skulle du jämföra ett engelskt ord med ett persiskt ord? En av problemförfattarna vet visserligen hur persiska ord ska uttalas, men utan den kunskapen blir det svårt.

Antag nu att vi vill sammanställa en sorterad lista av ord. Till vår hjälp har vi ett antal personer som vardera känner igen ett antal ord och vet deras inbördes ordning. Vi behöver inte ta med alla ord i vår ordlista, men vi vill vara helt säkra på att de ord vi tar med är rätt sorterade. Skriv ett program som beräknar det maximala antalet ord vi kan ha med i ordlistan, och skriver ut en giltig ordlista med detta antal ord.

Indata

För enkelhets skull behöver du inte läsa in själva orden, utan varje ord representeras istället av ett index mellan $0$ och $N-1$. På första raden av indatan står två heltal $N$ ($1 \leq N \leq 130000$) och $P$ ($1 \leq P \leq 10^5$), där $N$ är antalet ord och $P$ är antalet personer. Därefter följer $P$ rader som vardera anger ordningen på de ord som en viss person känner till. Varje sådan rad börjar med ett heltal $2 \leq p_ i \leq 25$ som beskriver hur många ord personen i fråga känner till den inbördes sorteringen för. Sedan följer $p_ i$ heltal i intervallet $0$ till $N-1$, indexen för de ord personen känner till i den ordning de ska sorteras. Det är inte säkert att alla de $N$ orden finns med på någon lista, och ett ord kan givetvis förekomma på flera listor. Det kommer inte att finnas motsägelser i indatan.

Delpoäng: För 30% av poängen gäller att $N \le 30$.

Utdata

På första raden ska programmet skriva ut det maximala antalet ord $M$ i en garanterat korrekt sorterad ordlista. Därefter ska programmet skriva ut en rad med en sådan sorterad ordlista innehållandes de $M$ ordindexen. Om det finns flera tänkbara sådana ordlistor kan programmet skriva vilken som helst av dem.

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

4
0 2 1 3 

10 6
2 5 7
3 4 2 0
4 4 8 1 0
3 8 2 5
2 0 6
3 4 7 9

6
4 8 2 5 7 9