/* affect.c (Problèmes d'affectations couplages) */
// *INDENT-OFF*
/*
 * affect.c (Problèmes d'affectations couplages) Recherche exhaustive de
 * tous les couplages de X dans Y d'un graphe biparti G(X, Y, E) avec |X|
 * inférieur ou égal à |Y| 
 *
 * Copyright (C) 2006 Jean-Paul Davalan <jpdvl.wanadoo.fr>
 * 
 * This program is free software; you can redistribute it and/or modify it 
 * under the terms of the GNU General Public License as published by the
 * Free Software Foundation; either version 2 of the License, or (at your
 * option) any later version.
 * 
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 * 
 * You should have received a copy of the GNU General Public License along 
 * with this program; if not, write to the Free Software Foundation, Inc., 
 * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 * 
 * compilation : 
 *                gcc -O2 -o affect affect.c 
 * usage :
 *                affect < essai1.txt 
 *
 * les solutions sont les lignes non
 * préfixées par le signe # les solutions ont le même format que celles
 * de la page web 
 * le format du fichier essai1.txt est particulier à l'application C 
 * La première ligne contient les deux valeurs de k et de n, ensuite 
 * pour chaque x de X (de 0 à k-1) x nb_images image image ...
 * (les images ont des valeurs comprises entre 0 et n-1) 
 * Exemple de fichier lu :
 * 5 5 k=5 n=5 
 * 0 3 0 1 2         x_0 a 3 images y_0 y_1 y_2 
 * 1 2 0 4           x_1 a 2 images 0 4 
 * 2 2 1 3 
 * 3 2 0 2 
 * 4 3 1 2 3         x_4 a 3 images 1 2 3 
 * (pour simplifier x_i est confondu avec i et y_j avec j) 
 *
 * Explications des couplages sur la page
 * --------------------------------------
 * http://perso.wanadoo.fr/jean-paul.davalan/mots/comb/affect/affect.html
 * le programme C et plusieurs fichiers essaiN.txt d'exemples :
 * affect.tar.gz 
 * les exemples sont entrés sous un autre format dans le programme javascript 
 * de cette page mais les exemples construits aléatoirements sont donnés sous les deux 
 * formats
 * 
 * C'est seulement ce second texte qui peu être lu par le programme C,
 * c'est donc lui qui doit être recopié dans un fichier "essai.txt"
 *
 * indent -br -ce -cdw -cli2 -cbi0 -ss -cs -bs -saf -nbc -psl -brs -ip2 -cdb affect.c
 */
// *INDENT-ON*

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct img {
  int x, m, *succ;
} img;

typedef struct affect {
  int k, n;
  img *pre;
} affect;

int nsols = 0;

affect *
lect ()
{
  affect *af = (affect *) malloc (sizeof (affect));
  int i, j, a, m, u, k, n;
  scanf ("%d %d", &k, &n);
  printf ("%d %d\n", k, n);
  af->k = k;
  af->n = n;
  af->pre = (img *) malloc (k * sizeof (img));
  for (i = 0; i < k; i++) {
    scanf ("%d %d", &a, &m);
    printf ("%d %d ", a, m);
    af->pre[a].x = a;
    af->pre[a].m = m;
    af->pre[a].succ = (int *) malloc (m * sizeof (int));
    for (j = 0; j < m; j++) {
      scanf ("%d", &u);
      printf (" %d", u);
      af->pre[a].succ[j] = u;
    }
    printf ("\n");
  }
  printf ("---\n");
  return af;
}

void
del (affect * l)
{
  int i, k = l->k;
  for (i = 0; i < k; i++) {
    free (l->pre[i].succ);
  }
  free (l->pre);
  free (l);
}

void
avance (affect * l, int kcur, int pk[], int p[])
{
  int k = l->k, n = l->n, p0[n];

  if (kcur < 0) {		// solution
    int i;
    for (i = 0; i < k; i++) {
      printf ("%d", pk[i]);
      if (i < k - 1)
	printf (" ");
    }
    printf ("\n");
    nsols++;
  } else {
    int i, j, m;
    for (i = 0; i < n; i++) {
      p0[i] = p[i];
    }
    for (j = 0; j < l->pre[kcur].m; j++) {
      m = l->pre[kcur].succ[j];
      if (p[m] == 0) {
	pk[kcur] = m;
	p0[m] = 1;
	avance (l, kcur - 1, pk, p0);
	p0[m] = 0;
      }
    }
  }
}

void
lance (affect * l)
{
  int i, k = l->k, n = l->n, pk[k], p[n];
  for (i = 0; i < k; i++) {
    pk[i] = 0;
  }
  for (i = 0; i < n; i++) {
    p[i] = 0;
  }
  avance (l, k - 1, pk, p);
}


int
main ()
{
  affect *l = lect ();
  nsols = 0;
  lance (l);
  printf ("# Nombre de solutions : %d\n", nsols);
  del (l);
  return 0;
}