Problem D
Plockepinn

Fröken Asplöv har blivit övertalad av en god vän att spela Plockepinn. I spelet Plockepinn ligger det en massa pinnar utslängda i en hög. Ett drag går ut på att försöka plocka upp en pinne utan att någon annan pinne rör på sig. Om man lyckas får man pinnen och för att vinna ska man ha flest pinnar i slutet av spelet.

Mer formellt kan man säga att det finns $N$ olika pinnar som beror på grupper av andra pinnar. En grupp är en mängd pinnar sådan att man kan ta bort alla pinnar i gruppen utom en utan att pinnarna som beror på gruppen rör på sig. Notera att en pinne kan ingå i flera grupper och att alla pinnar inte behöver ingå i någon grupp.

Det visar sig dock vara ett spel som inte passar Fröken Asplöv särskilt bra eftersom hon har väldigt lätt för att darra på handen. Därför har hon bestämt sig för att enbart spela Plockepinn mot sig själv så att hon slipper förlora hela tiden. Hon inser dock att det är svårare sagt än gjort, hur vet man vilken ordning man ska plocka pinnarna i? Eller om det överhuvudtaget är möjligt? Nu vill Fröken Asplöv ha din hjälp att hitta en ordning som hon kan plocka pinnarna i eller avgöra att det inte går.

Indata

Första raden innehåller två heltal, $N$ och $G$ ($N \geq 1, G \geq 0$), där $N$ är antalet pinnar som finns och $G$ är antalet unika grupper av pinnar.

Sedan följer en tom rad. Därefter följer $G$ rader som beskriver grupperna. På rad $i$ finns grupp $i$ och varje rad inleds med ett heltal $g_k$, hur många pinnar gruppen innehåller. Därefter följer $g_k$ heltal som beskriver pinnarnas index.

Efter det kommer en tom rad.

Sedan följer $N$ rader som beskriver pinnarna. På rad $i$ finns pinne $i$ och varje rad inleds med ett heltal $n_k$, hur många grupper pinnen beror på. Därefter följer $n_k$ heltal som beskriver gruppernas index.

Det är garanterat att indatan innehåller som mest $3 \cdot 10^5$ tal totalt.

Utdata

Skriv ut en rad med $N$ heltal, index för pinnarna du plockar bort i ordningen du plockar bort dem. Om det finns flera giltiga ordningar går det bra att skriva ut vilken som helst av dem.

Om det inte går att plocka bort alla pinnar ska du skriva ut ”impossible”.

Poängsättning

Din lösning kommer att testas på flera olika testgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.

Förklaring

I det första exempelfallet beror ingen pinne på pinne $4$. Därför kan vi ta bort den först. Av pinnarna som är kvar beror ingen på pinne $3$, därför tar vi bort den näst. Sedan beror ingen pinne på pinne $2$ så vi kan ta bort den. Till sist beror ingen pinne på pinne $1$, så vi tar bort den också. Det ger oss ordningen $4$ - $3$ - $2$ - $1$.

I det andra exempelfallet beror alla pinnarna på varandra och vi kan inte ta bort någon alls till att börja med. Därför är det omöjligt att hitta en ordning att ta bort pinnarna i.

I det tredje exempelfallet kan vi först ta bort pinne $1$. Det är ett giltigt drag eftersom även om pinne $2$ beror på grupp $2$ som pinne $1$ är med i, så finns fortfarande pinne $3$ kvar vilket gör att pinne $2$ inte rör på sig. Därefter finns det inga pinnar kvar som beror på pinne $2$ så vi kan ta bort den. Och eftersom pinne $3$ och $4$ inte beror på varandra kan vi slutligen ta bort dem också. Ett exempel på en giltig ordning är därför $1$ - $2$ - $4$ - $3$.

4 3

1 1
1 2
1 3

0
1 1
2 1 2
3 1 2 3

4 3 2 1

3 3

1 1
1 2
1 3

1 2
1 3
1 1

impossible

4 3

1 2
2 1 3
2 3 4

1 1
2 2 3
0
0

1 2 4 3