#include<stdio.h>
#include<malloc.h>

typedef int bool;
#define TRUE  1
#define FALSE 0

#define MALLOC(t) (t *)malloc(sizeof(t))
#define MALLOC_ARRAY(n,t) (t *)malloc(n*sizeof(t))

#define NO_DEBUG

#ifdef DEBUG
#define DEBUG_(X) X
#define DEBUG_P1(S,A) printf(S,A)
#define DEBUG_P2(S,A,B) printf(S,A,B)
#define DEBUG_P3(S,A,B,C) printf(S,A,B,C)
#define DEBUG_I(N) printf("%*s", (N)*3, "");
#else
#define DEBUG_(X)
#define DEBUG_P1(S,A)
#define DEBUG_P2(S,A,B)
#define DEBUG_P3(S,A,B,C)
#define DEBUG_I(N)
#endif
#define _DEBUG_(X)
#define _DEBUG_P1(S,A)
#define _DEBUG_P2(S,A,B)
#define _DEBUG_P3(S,A,B,C)
#define _DEBUG_I(N)

bool opt_count = FALSE;
bool opt_write = FALSE;
bool opt_graph = FALSE;

 
typedef struct T_piece
{   int nr_orients;
    struct T_orient **orients;
    int nr_poss;
    bool placed;
    int nr;
} t_piece;

int nr_pieces;
t_piece *pieces = NULL;

typedef struct T_orient
{   int nr_locs;
    struct T_loc **locs;
    t_piece *of_piece;
    int ignored;
    int nr;
} t_orient;

int nr_orients;
t_orient **orients = NULL;

typedef struct T_loc
{   int nr_in_orients;
    t_orient **in_orients;
    int covered;        /* cur nr of orientations that cover it */
    int piece;          /* nr of piece placed */
    int nr;
} t_loc;

int nr_locs;
t_loc *locs = NULL;

int count = 0;

void print_state()
{   int p, l;

    for (p = 0; p < nr_pieces; p++)
    {   t_piece *piece = pieces + p;

        printf("%d,%d: ", piece->placed, piece->nr_poss);

        /* for (o = 0; o < piece->nr_orients; o++)
            printf("%d ", piece->orients[o]->ignored); */
    }
    printf("|");

    for (l = 0; l < nr_locs; l++)
        printf(" %d:%d", locs[l].covered, locs[l].piece);
    printf("\n");
}

void read_puzzle(FILE *fin)
{   int p, l, o_nr = 0;

    fscanf(fin, "%d %d", &nr_locs, &nr_pieces);

    _DEBUG_P1("nr_locs: %d\n", nr_locs);
    _DEBUG_P1("nr_pieces: %d\n", nr_pieces);

    pieces = MALLOC_ARRAY(nr_pieces, t_piece);
    locs = MALLOC_ARRAY(nr_locs, t_loc);

    nr_orients = 0;

    for (l = 0; l < nr_locs; l++)
    {   locs[l].nr_in_orients = 0;
        locs[l].nr = l;
    }

    for (p = 0; p < nr_pieces; p++)
    {   int o_p;

        fscanf(fin, "%d", &pieces[p].nr_orients);

        _DEBUG_P2("piece %d, nr_orient: %d\n", p, pieces[p].nr_orients);

        pieces[p].orients = MALLOC_ARRAY(pieces[p].nr_orients, t_orient *);
        pieces[p].nr_poss = pieces[p].nr_orients;
        pieces[p].placed = FALSE;
        pieces[p].nr = p;

        for (o_p = 0; o_p < pieces[p].nr_orients; o_p++)
        {   int l;
            t_orient *orient = MALLOC(t_orient);

            pieces[p].orients[o_p] = orient;
            orient->of_piece = pieces + p;
            orient->nr = nr_orients++;
            orient->ignored = 0;

            fscanf(fin, "%d", &orient->nr_locs);

            _DEBUG_P2("orient %d, nr_loc: %d\n", o_p, orient->nr_locs);

            orient->locs = MALLOC_ARRAY(orient->nr_locs, t_loc *);

            for (l = 0; l < orient->nr_locs; l++)
            {   int lnr;
                fscanf(fin, "%d", &lnr);
                if (lnr < 0 || lnr >= nr_locs)
                {   fprintf(stderr, 
                            "Error: Piece %d, orientation %d, found %d\n",
                            p, o_p, lnr);
                    exit(1);
                }
                _DEBUG_P1("  loc: %d\n", lnr);
                orient->locs[l] = locs + lnr;
                locs[lnr].nr_in_orients++;
            }
        }
    }

    for (l = 0; l < nr_locs; l++)
    {   locs[l].in_orients = MALLOC_ARRAY(locs[l].nr_in_orients, t_orient *);
        locs[l].covered = locs[l].nr_in_orients;
        locs[l].nr_in_orients = 0;
        locs[l].piece = -1;
    }

    orients = MALLOC_ARRAY(nr_orients, t_orient *);
    o_nr = 0;

    for (p = 0; p < nr_pieces; p++)
    {   int o_p;

        for (o_p = 0; o_p < pieces[p].nr_orients; o_p++)
        {   t_orient *orient = pieces[p].orients[o_p];

            orients[o_nr++] = orient;

            for (l = 0; l < orient->nr_locs; l++)
            {   t_loc *loc = orient->locs[l];

                loc->in_orients[loc->nr_in_orients++] = orient;
            }
        }
    }
}

void write_puzzle(FILE *fout)
{   int p;

    fprintf(fout, "%d %d\n", nr_locs, nr_pieces);

    for (p = 0; p < nr_pieces; p++)
    {   int o_p;

        fprintf(fout, "  %d\n", pieces[p].nr_orients);

        for (o_p = 0; o_p < pieces[p].nr_orients; o_p++)
        {   int l;
            t_orient *orient = pieces[p].orients[o_p];

            fprintf(fout, "      %d ", orient->nr_locs);

            for (l = 0; l < orient->nr_locs; l++)
                fprintf(fout, " %d", orient->locs[l]->nr);
            fprintf(fout, "\n");
        }
    }
}



void choose(int pieces_left, t_piece *p, t_orient *s_o);

void fit(int pieces_left)
{   int l,
        p, 
        min_p = -1,
        min_p_v,
        min_l = -1,
        min_l_v;

    DEBUG_I(nr_pieces - pieces_left);
    DEBUG_P1("  fit(%d);\n", pieces_left);

    if (pieces_left == 1)
        if (opt_count)
        {   count++;
            if (count % 100 == 0)
                printf("%d\n", count);
            return;
        }
        else
        {   int p;
            int l;

            for (p = 0; p < nr_pieces; p++)
                if (!pieces[p].placed)
                    break;

            for (l = 0; l < nr_locs; l++)
                printf("%d, ", locs[l].piece == -1 ? p : locs[l].piece);
            printf("\n");
            return;
        }     
    pieces_left--;

    /* Find location with only one orientation */
    for (l = 0; l < nr_locs; l++)
        if (locs[l].piece == -1)
        {   int c = locs[l].covered == 1;

            if (c == 1)
            {   int io;

                for (io = 0; io < locs[l].nr_in_orients; io++)
                {   t_orient *orient = locs[l].in_orients[io];

                    if (orient->ignored == 0)
                    {   choose(pieces_left, orient->of_piece, orient);
                        return;
                    }
                }
            }
            else if (c < min_l_v || min_l == -1)
            {   min_l_v = c;
                min_l = l;
            }
        }

    /* Find piece with min number of orientations */
    for (p = 0; p < nr_pieces; p++)
        if (!pieces[p].placed)
            if (min_p == -1 || pieces[p].nr_poss < min_p_v)
            {   min_p = p;
                min_p_v = pieces[p].nr_poss;
            }

    /* Try all possible orientations of this piece */
    if (min_p_v <= min_l_v)
    {   int p_o;

        for (p_o = 0; p_o < pieces[min_p].nr_orients; p_o++)
        {   t_orient *orient = pieces[min_p].orients[p_o];

            if (orient->ignored == 0)
                choose(pieces_left, &pieces[min_p], orient);
        }
    }
    else
    {   int io;

        for (io = 0; io < locs[min_l].nr_in_orients; io++)
        {   t_orient *orient = locs[min_l].in_orients[io];

            if (orient->ignored == 0)
                choose(pieces_left, orient->of_piece, orient);
        }
    }

    DEBUG_I(nr_pieces - pieces_left - 1);
    DEBUG_P1("  ready fit(%d);\n", pieces_left);
}

void choose(int pieces_left, t_piece *p, t_orient *s_o)
{   bool impossible = FALSE;
    int l, l_max, p_o, p_o_max, i;

    DEBUG_I(nr_pieces - pieces_left);
    DEBUG_P3("choose(,%d,%d) : nr_poss=%d;\n", p->nr, s_o->nr, p->nr_poss);
    DEBUG_(print_state();)

    /* mark piece placed: */
    p->placed = TRUE;

    /* mark locations of orient selected: */
    for (l = 0; l < s_o->nr_locs; l++)
        s_o->locs[l]->piece = p->nr;

    for (l = 0; l < s_o->nr_locs && !impossible; l++)
    {   t_loc *loc = s_o->locs[l];

        DEBUG_I(nr_pieces - pieces_left);
        DEBUG_P1(" mark loc %d\n", loc->nr);

        /* for each of the locations, mark other orientations as
           not used: */
        for (i = 0; i < loc->nr_in_orients; i++)
        {   t_orient *o_i = loc->in_orients[i];

            if (o_i != s_o)
            {   DEBUG_I(nr_pieces - pieces_left);
                DEBUG_P2(" ignore orient %d (%d)\n", 
                         o_i->nr, o_i->ignored);
                o_i->ignored++;
                if (o_i->ignored == 1)
                {   /* first time ignored: */
                    int l;

                    /* reduce possible count for piece of orientation: */
                    DEBUG_I(nr_pieces - pieces_left);
                    DEBUG_P1("    of piece %d\n", o_i->of_piece->nr);
                    if (--o_i->of_piece->nr_poss == 0)
                        impossible = TRUE;

                    /* update locations covered by this orientation: */
                    for (l = 0; l < o_i->nr_locs; l++)
                    {   
                        DEBUG_I(nr_pieces - pieces_left);
                        DEBUG_P1("    reduce loc %d\n", loc->nr);
                        if (--o_i->locs[l]->covered == 0)
                            impossible = TRUE;
                    }
                }
            }
        }
    }
    l_max = l;
    DEBUG_(print_state();)

    if (!impossible)
    {   /* select orientation */
        for (p_o = 0; p_o < p->nr_orients && !impossible; p_o++)
        {   t_orient *o = p->orients[p_o];
    
            if (o != s_o)
            {   DEBUG_I(nr_pieces - pieces_left);
                DEBUG_P2(" ignore orient %d (%d)\n", o->nr, o->ignored);
                o->ignored++;
                if (o->ignored == 1)
                {   /* first time ignored: */
                    int l;

                    /* lower value of its locations */
                    for (l = 0; l < o->nr_locs; l++)
                    {   
                        DEBUG_I(nr_pieces - pieces_left);
                        DEBUG_P1("  reduce loc %d\n", o->locs[l]->nr);
                        if (--o->locs[l]->covered == 0)
                            impossible = TRUE;
                    }
                }
            }
        }
        p_o_max = p_o;


        if (!impossible)
            fit (pieces_left);

        /* deselect orientation */
        for (p_o = 0; p_o < p_o_max; p_o++)
        {   t_orient *o = p->orients[p_o];
        
            if (o != s_o)
            {   DEBUG_I(nr_pieces - pieces_left);
                DEBUG_P2(" unignore orient %d (%d)\n", o->nr, o->ignored);
               
                if (o->ignored == 1)
                {   /* first time ignored: */
                    int l;
    
                    /* lower value of its locations */
                    for (l = 0; l < o->nr_locs; l++)
                    {   
                        DEBUG_I(nr_pieces - pieces_left);
                        DEBUG_P1("  increase loc %d\n", o->locs[l]->nr);
                        o->locs[l]->covered++;
                    }
                }
                o->ignored--;
            }
        }
        DEBUG_(print_state();)
    }

    /* unmark locations of orient selected: */
    for (l = 0; l < l_max; l++)
    {   t_loc *loc = s_o->locs[l];

        DEBUG_I(nr_pieces - pieces_left);
        DEBUG_P1(" unmark loc %d\n", loc->nr);

        /* for each of the locations, unmark other orientations as
           not used: */
        for (i = 0; i < loc->nr_in_orients; i++)
        {   t_orient *o_i = loc->in_orients[i];

            if (o_i != s_o)
            {   DEBUG_I(nr_pieces - pieces_left);
                DEBUG_P2(" unignore orient %d (%d)\n", 
                         o_i->nr, o_i->ignored - 1);
                if (o_i->ignored == 1)
                {   /* first time ignored: */
                    int l;

                    /* increase possible count for piece of orientation: */
                    DEBUG_I(nr_pieces - pieces_left);
                    DEBUG_P1("    of piece %d\n", o_i->of_piece->nr);
                    o_i->of_piece->nr_poss++;

                    /* update locations covered by this orientation: */
                    for (l = 0; l < o_i->nr_locs; l++)
                    {   
                        DEBUG_I(nr_pieces - pieces_left);
                        DEBUG_P1("    increase loc %d\n", loc->nr);
                        o_i->locs[l]->covered++;
                    }
                }
                o_i->ignored--;
            }
        }
    }
    for (l = 0; l < s_o->nr_locs; l++)
        s_o->locs[l]->piece = -1;

    p->placed = FALSE;

    DEBUG_(print_state();)


    DEBUG_I(nr_pieces - pieces_left);
    DEBUG_P2("ready choose(,%d,%d);\n", p->nr, s_o->nr);
}
    
    
void print_graph()
{   int i, j;

    for (i = 0; i < nr_orients; i++)
    {   for (j = 0; j < nr_orients; j++)
            if (i == j)
                printf("  ");
            else if (orients[i]->of_piece == orients[j]->of_piece)
                printf(" x");
            else
            {   bool found = FALSE;
                t_orient *o_i = orients[i],
                         *o_j = orients[j];
                int k,l;

                for (k = 0; k < o_i->nr_locs && !found; k++)
                    for (l = 0; l < o_j->nr_locs && !found; l++)
                        if (o_i->locs[k] == o_j->locs[l])
                            found = TRUE;

                printf(found ? " x" : "  ");
            }
        printf("\n");
    }
}

void main(int argc, char *argv[])
{   int i;

    for (i = 0; i < argc; i++)
        if (!strcmp(argv[i], "-c"))
            opt_count = TRUE;
        else if (!strcmp(argv[i], "-w"))
            opt_write = TRUE;
        else if (!strcmp(argv[i], "-g"))
            opt_graph = TRUE;
    
    read_puzzle(stdin);
    if (opt_write)
        write_puzzle(stdout);
    if (opt_graph)
        print_graph();
    fit(nr_pieces);
    if (opt_count)
        printf("\nTotal: %d\n", count);
}