Selecció musical X93236

Després d’un any de moltes penúries, per aixecar els ànims decideixes organitzar unes vacances amb uns amics en un racó perdut a la muntanya. Com que a tots els amics els agrada molt la música, però d’estils molt diferents, per tal que les vacances surtin bé és important que, durant el trajecte en cotxe, tothom pugui escoltar cançons del seu gust. Malauradament, la llista de totes les cançons que els amics voldrien escoltar és interminable, i el viatge en cotxe és llarg però no tant. Per això acordeu conformar-vos si cadascú pot escoltar almenys una de les seves cançons preferides. Pots encarregar-te tu de la selecció musical?

Entrada

L’entrada només conté nombres enters. Comença amb $n$, el nombre de cançons que es poden escollir. Segueix $m$, el nombre d’amics, i després $m$ línies, cadascuna de les quals comença amb $s_{i}$, el nombre de cançons preferides de l’amic $i$-èsim, seguit de les corresponents $s_{i}$ cançons. Cada cançó s’identifica amb un nombre entre $0$ i $n-1$. L’entrada acaba amb $k$, el nombre màxim de cançons que es poden escollir. Podeu assumir que $1 \leq n \leq 25$, que $1 \leq m \leq 250$, i que $1 \leq s_{i}, k \leq n$.

Sortida

Escriviu totes les seleccions de com a molt $k$ cançons tals que cada amic pot escoltar almenys una de les seves cançons preferides. A cada selecció cal escriure les cançons en ordre creixent d’identificador. Les seleccions es poden escriure en ordre arbitrari.

Observació

Heu d’implementar un poda que descarti les solucions parcials quan ja no es poden estendre de forma que tots els amics quedin satisfets.