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

#define DEBUG_(X) fprintf(stderr,X)
#define DEBUG_P1(S,A) fprintf(stderr,S,A)
#define DEBUG_P2(S,A,B) fprintf(stderr,S,A,B)
#define DEBUG_P3(S,A,B,C) fprintf(stderr,S,A,B,C)
#define DEBUG_I(N) printf("%*s", (N)*3, "");

const char* at_debug = "";

template <class T, class S>
class Chain
{
public:
    Chain(T* n_owner = 0, S* n_parent = 0) : next(this), prev(this), owner(n_owner), parent(n_parent), r(false) {}
    bool isEmpty() { return next == this; }
    void push_back(Chain<T,S>* chain)
    {
        chain->prev = prev;
        prev->next = chain;
        prev = chain;
        chain->next = this;
    }
    void remove()
    {
        //DEBUG_P2("%sremove: %p\n", at_debug, this);
        next->prev = prev;
        prev->next = next;
        if (r)
        {
            fprintf(stderr, "\nError in remove: %p\n", this);
            exit(1);
        }
        r = true;
    }
    void undo_remove()
    {
        //DEBUG_P2("%sundo_remove: %p\n", at_debug, this);
        next->prev = this;
        prev->next = this;
        if (!r)
        {
            fprintf(stderr, "\nError in undo_remove: %p\n", this);
            exit(1);
        }
        r = false;
    }
    
    class Iterator
    {
    public:
        Iterator(Chain<T,S>& chain) { _end = &chain; _cur = chain.next; }
        Iterator(Iterator& it) { _end = it._end; _cur = it._cur; }
        bool more() { return _cur != _end; }
        void next() { _cur = _cur->next; }
        T* owner() { return _cur->owner; }
        S* parent() { return _cur->parent; }
    private:
        Chain<T,S>* _end;
        Chain<T,S>* _cur;
    };
    class ReverseIterator
    {
    public:
        ReverseIterator(Chain<T,S>& chain) { _end = &chain; _cur = chain.prev; }
        ReverseIterator(Iterator& it) { _end = it._end; _cur = it._cur; }
        bool more() { return _cur != _end; }
        void next() { _cur = _cur->prev; }
        T* owner() { return _cur->owner; }
        S* parent() { return _cur->parent; }
    private:
        Chain<T,S>* _end;
        Chain<T,S>* _cur;
    };
    
    Chain<T,S>* next;
    Chain<T,S>* prev;
    T* owner;
    S* parent;
    bool r;
};

    
template <class T>
class Neighbour
{
public:
    typedef Chain<Neighbour<T>,T> NChain;
    
    Neighbour(T* e1, NChain& c1, T* e2, NChain& c2)
      : chain1(this, e1), chain2(this, e2)
    {
        c1.push_back(&chain1);
        c2.push_back(&chain2);
    }

    void remove(NChain* c)
    {
        if (&chain1 == c)
            chain2.remove();
        else
            chain1.remove();
    }
    void undo_remove(NChain* c)
    {
        if (&chain1 == c)
            chain2.undo_remove();
        else
            chain1.undo_remove();
    }

    class Iterator
    {
    public:
        Iterator(NChain& chain) { _end = &chain; _cur = chain.next; }
        Iterator(Iterator& it) { _end = it._end; _cur = it._cur; }
        bool more() { return _cur != _end; }
        void next() { _cur = _cur->next; }
        T* value()
        {
            Neighbour* neighbour = _cur->owner;
            return &neighbour->chain1 == _cur ? neighbour->chain2.parent : neighbour->chain1.parent;
        }
        void remove() { _cur->owner->remove(_cur); }
        //void undo_remove() { _cur->owner->undo_remove(_cur); }
    private:
        NChain* _end;
        NChain* _cur;
    };
    class ReverseIterator
    {
    public:
        ReverseIterator(NChain& chain) { _end = &chain; _cur = chain.prev; }
        ReverseIterator(Iterator& it) { _end = it._end; _cur = it._cur; }
        bool more() { return _cur != _end; }
        void next() { _cur = _cur->prev; }
        T* value()
        {
            Neighbour* neighbour = _cur->owner;
            return &neighbour->chain1 == _cur ? neighbour->chain2.parent : neighbour->chain1.parent;
        }
        //void remove() { _cur->owner->remove(_cur); }
        void undo_remove() { _cur->owner->undo_remove(_cur); }
    private:
        NChain* _end;
        NChain* _cur;
    };

    NChain chain1;
    NChain chain2;
};

class PiecePlacement;
typedef Neighbour<PiecePlacement> PiecePlacementNeighbour;
typedef PiecePlacementNeighbour::NChain PPNChain;

class Cell;
class PiecePlacementUseCell;
typedef Chain<PiecePlacementUseCell, PiecePlacement> CAPPChain;
typedef Chain<PiecePlacementUseCell, Cell> PPUCChainBase;
class PPUCChain : public PPUCChainBase
{
public:
    PPUCChain(PiecePlacementUseCell* owner = 0, Cell* parent = 0) : PPUCChainBase(owner, parent) {}
    void push_back(PPUCChain* chain);
    void remove();
    void undo_remove();
};

class PiecePlacementUseCell
{
public:
    PiecePlacementUseCell(PiecePlacement* pp, Cell* cell)
      : pp_chain(this, cell), c_chain(this, pp) {}

    class CellsIterator
    {
    public:
        CellsIterator(CAPPChain& chain) { _end = &chain; _cur = chain.next; }
        //CellsIterator(CellsIterator& it) { _end = it._end; _cur = it._cur; }
        bool more() { return _cur != _end; }
        void next() { _cur = _cur->next; }
        Cell* cell() { return _cur->owner->pp_chain.parent; }
        void remove() { _cur->owner->pp_chain.remove(); }
        //void undo_remove() { _cur->owner->pp_chain.undo_remove(_cur); }
    private:
        CAPPChain* _end;
        CAPPChain* _cur;
    };
    class ReverseCellsIterator
    {
    public:
        ReverseCellsIterator(CAPPChain& chain) { _end = &chain; _cur = chain.prev; }
        //ReverseCellsIterator(ReverseCellsIterator& it) { _end = it._end; _cur = it._cur; }
        bool more() { return _cur != _end; }
        void next() { _cur = _cur->prev; }
        Cell* cell() { return _cur->owner->pp_chain.parent; }
        //void remove() { _cur->owner->pp_chain.remove(_cur); }
        void undo_remove() { _cur->owner->pp_chain.undo_remove(); }
    private:
        CAPPChain* _end;
        CAPPChain* _cur;
    };

    class PiecePlacementIterator
    {
    public:
        PiecePlacementIterator(PPUCChain& chain) { _end = &chain; _cur = chain.next; }
        //PiecePlacementIterator(CellsIterator& it) { _end = it._end; _cur = it._cur; }
        bool more() { return _cur != _end; }
        void next() { _cur = _cur->next; }
        PiecePlacement* piecePlacement() { return _cur->owner->c_chain.parent; }
        void remove() { _cur->owner->c_chain.remove(); }
        //void undo_remove() { _cur->owner->c_chain.undo_remove(); }
    private:
        PPUCChainBase* _end;
        PPUCChainBase* _cur;
    };
    class ReversePiecePlacementIterator
    {
    public:
        ReversePiecePlacementIterator(PPUCChain& chain) { _end = &chain; _cur = chain.prev; }
        //ReversePiecePlacementIterator(ReverseCellsIterator& it) { _end = it._end; _cur = it._cur; }
        bool more() { return _cur != _end; }
        void next() { _cur = _cur->prev; }
        PiecePlacement* piecePlacement() { return _cur->owner->c_chain.parent; }
        //void remove() { _cur->owner->c_chain.remove(); }
        void undo_remove() { _cur->owner->c_chain.undo_remove(); }
    private:
        PPUCChainBase* _end;
        PPUCChainBase* _cur;
    };
        
    PPUCChain pp_chain;
    CAPPChain c_chain;
};

typedef Neighbour<Cell> CellNeighbour;
typedef Chain<Cell, void> CellChain;

class Cell
{
public:
    Cell() : nr_piece_placements(0), chain(this), accepted_placement(0) {}
    int nr;
    PPUCChain piece_placements;
    int nr_piece_placements;
    CellNeighbour::NChain neighbours;
    
    PiecePlacement* accepted_placement;
    
    int covered_by_placement;
    
    CellChain chain;
};

void PPUCChain::push_back(PPUCChain* chain)
{
    PPUCChainBase::push_back(chain);
    chain->parent->nr_piece_placements++;
}
void PPUCChain::remove()
{
    PPUCChainBase::remove();
    //DEBUG_P2("%s-- %p\n", at_debug, parent);
    parent->nr_piece_placements--;
}
void PPUCChain::undo_remove()
{
    PPUCChainBase::undo_remove();
    //DEBUG_P2("%s++ %p\n", at_debug, parent);
    parent->nr_piece_placements++;
}

class Piece;
typedef Chain<Piece,void> PieceChain;
typedef Chain<PiecePlacement,Piece> PPChain;

const int plurality = 5;

class Piece
{
public:
    Piece() : chain(this), nr_sel_placements(0) {}
    PiecePlacement* newPlacement();
    
    char name;
    
    PPChain placements;

    bool all_selected() { return nr_sel_placements == plurality; }
    void add_selected(PiecePlacement* placement) { sel_placements[nr_sel_placements++] = placement; }
    void remove_selected(PiecePlacement* placement) { nr_sel_placements--; }
    int nr_sel_placements;
    PiecePlacement* sel_placements[plurality];
    
    void remove();
    void undo_remove();
        
    PieceChain chain;
};

class PiecePlacement
{
public:
    PiecePlacement(Piece* piece) : chain(this, piece), accepted(false), possible(false), possible_at(0) {}
     
    void addCell(Cell *cell)
    {
        PiecePlacementUseCell* ppuc = new PiecePlacementUseCell(this, cell);
        cells.push_back(&ppuc->c_chain);
        cell->piece_placements.push_back(&ppuc->pp_chain);
    }

    void remove(Cell *cell = 0)
    {
        // For neighbours
        for (PiecePlacementNeighbour::Iterator ppn_it(neighbours); ppn_it.more(); ppn_it.next())
            ppn_it.remove();

        // For cells            
        for (PiecePlacementUseCell::CellsIterator cell_it(cells); cell_it.more(); cell_it.next())
            if (cell_it.cell() != cell)
                cell_it.remove();
                
        chain.remove();
    }
    void undo_remove(Cell *cell = 0)
    {
        chain.undo_remove();
        
        // For cells            
        for (PiecePlacementUseCell::ReverseCellsIterator cell_it(cells); cell_it.more(); cell_it.next())
            if (cell_it.cell() != cell)
                cell_it.undo_remove();

        // For neighbours
        for (PiecePlacementNeighbour::ReverseIterator ppn_it(neighbours); ppn_it.more(); ppn_it.next())
            ppn_it.undo_remove();
    }
    
    void accept()
    {
        // For cells covered by this placement            
        for (PiecePlacementUseCell::CellsIterator cell_it(cells); cell_it.more(); cell_it.next())
        {
            Cell* cell = cell_it.cell();
        
            cell->accepted_placement = this;
            
            // Remove the cell from still available cells
            cell->chain.remove();
            
            // Remove all piece placements that have this cell, except ourselved of course
            for (PiecePlacementUseCell::PiecePlacementIterator pp_it(cell->piece_placements); pp_it.more(); pp_it.next())
            {
                PiecePlacement* overlapping_pp = pp_it.piecePlacement();
                
                if (overlapping_pp != this)
                    overlapping_pp->remove(cell);
            }
        }
        
        chain.parent->add_selected(this);
        if (chain.parent->all_selected())
        {
            chain.parent->remove();
        }
        
        accepted = true;
    }
    
    void undo_accept()
    {
        if (chain.parent->all_selected())
        {
            chain.parent->undo_remove();
        }
        chain.parent->remove_selected(this);
        
        // For cells covered by this placement        
        for (PiecePlacementUseCell::ReverseCellsIterator cell_it(cells); cell_it.more(); cell_it.next())
        {
            Cell* cell = cell_it.cell();

            cell->accepted_placement = 0;
            
            // Undo remove all piece placements that have this cell, except ourselved of course
            for (PiecePlacementUseCell::ReversePiecePlacementIterator pp_it(cell->piece_placements); pp_it.more(); pp_it.next())
            {
                PiecePlacement* overlapping_pp = pp_it.piecePlacement();
                
                if (overlapping_pp != this)
                    overlapping_pp->undo_remove(cell);
            }

            // Undo remove the cell from still available cells
            cell->chain.undo_remove();
            
        }
        
        accepted = false;
    }

    int nr;
    
    PPNChain neighbours;
    CAPPChain cells;
    
    PPChain chain;
    
    bool accepted;
    
    bool possible;
    int possible_at;
    
    PiecePlacement* next_removed;
};

PiecePlacement* Piece::newPlacement()
{
    PiecePlacement* result = new PiecePlacement(this);
    placements.push_back(&result->chain);
    
    return result;
}

void Piece::remove()
{
    for (PPChain::Iterator placement_it(placements); placement_it.more(); placement_it.next())
    {
        for (PiecePlacementUseCell::CellsIterator cell_it(placement_it.owner()->cells); cell_it.more(); cell_it.next())
            cell_it.remove();
    }
    
    chain.remove();
}

void Piece::undo_remove()
{
    chain.undo_remove();
    
    for (PPChain::ReverseIterator placement_it(placements); placement_it.more(); placement_it.next())
    {
        for (PiecePlacementUseCell::ReverseCellsIterator cell_it(placement_it.owner()->cells); cell_it.more(); cell_it.next())
            cell_it.undo_remove();
    }
}

void makeNeighbours(PiecePlacement* pp1, PiecePlacement* pp2)
{
    new PiecePlacementNeighbour(pp1, pp1->neighbours, pp2, pp2->neighbours);
}

Cell *cells;
CellChain all_cells;
PieceChain all_pieces;

void read_puzzle(FILE *fin)
{
    int nr_cells;
    int nr_pieces;   
    fscanf(fin, "%d %d", &nr_cells, &nr_pieces);
    //DEBUG_P1("nr_cells: %d\n", nr_cells);
    //DEBUG_P1("nr_pieces: %d\n", nr_pieces);

    cells = new Cell[nr_cells];
    for (int i = 0; i < nr_cells; i++)
    {
        cells[i].nr = i;
        all_cells.push_back(&cells[i].chain);
    }
    //DEBUG_("x\n");        
        
    Piece *pieces = new Piece[nr_pieces];
    for (int i = 0; i < nr_pieces; i++)
    {
        pieces[i].name = 'a' + i;
        all_pieces.push_back(&pieces[i].chain);
    }

    //DEBUG_("x\n");        
    for (int p = 0; p < nr_pieces; p++)
    {
        int nr_placements;
        fscanf(fin, "%d", &nr_placements);
        //DEBUG_P2("piece %d, nr_placements: %d\n", p, nr_placements);

        Piece* piece = &pieces[p];
        
        for (int o_p = 0; o_p < nr_placements; o_p++)
        {   
            PiecePlacement* placement = piece->newPlacement();
            placement->nr = o_p;
            
            int nr_pp_cells;
            fscanf(fin, "%d", &nr_pp_cells);

            //DEBUG_P2("placement %d, nr_cells: %d - ", o_p, nr_pp_cells);

            for (int l = 0; l < nr_pp_cells; l++)
            {   
                int lnr;
                fscanf(fin, "%d", &lnr);
                if (lnr < 0 || lnr >= nr_cells)
                {   fprintf(stderr, 
                            "Error: Piece %d, orientation %d, found %d\n",
                            p, o_p, lnr);
                    return;
                }
                //DEBUG_P1(" %d", lnr);
                
                placement->addCell(&cells[lnr]);
            }
            //DEBUG_("\n");
        }
    }
    
    int nr_neighbours;
    fscanf(fin, "%d", &nr_neighbours);
    
    for (int n = 0; n < nr_neighbours; n++)
    {
        int i,j;
        fscanf(fin, "%d %d", &i, &j);
        
        Cell* cell1 = &cells[i];    
        Cell* cell2 = &cells[j];
        new CellNeighbour(cell1, cell1->neighbours, cell2, cell2->neighbours);
    }
}

void find_neighbours()
{
    for (PieceChain::Iterator piece(all_pieces); piece.more(); piece.next())
    {
        int nr = 0;
        
        PPChain &placements = piece.owner()->placements;
        
        for (PPChain::Iterator placement1(placements); placement1.more(); placement1.next())
        {
            PPChain::Iterator placement2(placement1);
            for (placement2.next(); placement2.more(); placement2.next())
            {
                bool overlap = false;
                bool touching = false;
                
                for (CAPPChain::Iterator capp1(placement1.owner()->cells); capp1.more(); capp1.next())
                {
                    Cell *cell1 = capp1.owner()->pp_chain.parent;
                    
                    for (CAPPChain::Iterator capp2(placement2.owner()->cells); capp2.more(); capp2.next())
                    {
                        Cell *cell2 = capp2.owner()->pp_chain.parent;
                        
                        if (cell1 == cell2)
                            overlap = true;
                        
                        if (!overlap && !touching)
                        {
                            for (CellNeighbour::Iterator neighbour(cell1->neighbours); neighbour.more(); neighbour.next())
                                if (neighbour.value() == cell2)
                                {
                                    touching = true;
                                    break;
                                }
                        }
                    }
                }
                if (!overlap && touching)
                {
                    nr++;
                    makeNeighbours(placement1.owner(), placement2.owner());
                }
            }
        }
        DEBUG_P1("Piece %d\n", nr);
    }
}

void print_state(FILE* f)
{
    for (PieceChain::Iterator piece(all_pieces); piece.more(); piece.next())
    {
        fprintf(f, "Piece %p %p\n", piece.owner(), piece.parent());
        
        for (PPChain::Iterator placement(piece.owner()->placements); placement.more(); placement.next())
        {
            fprintf(f, "  placement(%d): ", placement.owner()->nr);
            
            for (CAPPChain::Iterator cell(placement.owner()->cells); cell.more(); cell.next())
            {
                fprintf(f, " %d", cell.owner()->pp_chain.parent->nr);
            }
            
            for (PiecePlacementNeighbour::Iterator neighbour(placement.owner()->neighbours); neighbour.more(); neighbour.next())
            {
                fprintf(f, " (%d)", neighbour.value()->nr);
            }
            
            fprintf(f, "\n");
        }
    }
    for (CellChain::Iterator cell_it(all_cells); cell_it.more(); cell_it.next())
    {
        fprintf(f, "Cell %d: %d\n", cell_it.owner()->nr, cell_it.owner()->nr_piece_placements);
    }
}

void print_solution(FILE* f)
{
    int n = 7;
    int m = 15;
#define CELL(X,Y) cells[(X)*m + (Y)]

//    int n = 3;
//    int m = 10;
//#define CELL(X,Y) cells[(X) + (Y)*n]

#if 0
    for (int j = 0; j < m; j++)
        fprintf(f, "+--");
    fprintf(f, "+\n");
        
    for (int i = 0; i < n; i++)
    {
        fprintf(f, "|%s", CELL(i,0).accepted_placement != 0 ? "  " : "##");
        for (int j = 0; j < m-1; j++)
            fprintf(f, "%c%s", CELL(i,j).accepted_placement == CELL(i,j+1).accepted_placement ? ' ' : '|', CELL(i,j+1).accepted_placement != 0 ? "  " : "##");
        fprintf(f, "|\n");

        if (i < n-1)
        {
            for (int j = 0; j < m; j++)
                fprintf(f, CELL(i,j).accepted_placement == CELL(i+1,j).accepted_placement ? "+  " : "+--");
            fprintf(f, "+\n");
        }
    }
    for (int j = 0; j < m; j++)
        fprintf(f, "+--");
    fprintf(f, "+\n\n");
#else
    fprintf(f, "p(\"");
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
            fprintf(f, "%c", CELL(i,j).accepted_placement->chain.parent->name);
    }
    fprintf(f, "\")\n");
#endif    

}

bool neighbours(PiecePlacement* a, PiecePlacement* b)
{
    for (PiecePlacementNeighbour::Iterator placement_it(a->neighbours); placement_it.more(); placement_it.next())
        if (placement_it.value() == b)
            return true;
            
    return false;
}

void print(PiecePlacement* placement)
{
    int i = 0;
    for (CAPPChain::Iterator cell_it(placement->cells); cell_it.more(); cell_it.next())
    {
        printf("%c%d", i == 0 ? ' ' : ',', cell_it.owner()->pp_chain.parent->nr);
        i++;
    }
}

void solve()
{
    static int depth = 0;
    //fprintf(stderr, " %d\n", ++depth);
    //print_solution(stdout);
        
    // First remove all pieces placements which cannot be placed, because they would make
    // it impossible for some cells to be covered.
    PiecePlacement* removed = 0;

    Piece* difficult_piece = 0;
    PiecePlacement* difficult_piece_placement;
    int difficult_piece_nr_placements;
        
    bool go = true;
    while (go)
    {
        go = false;
            
        for (PieceChain::Iterator piece_it(all_pieces); piece_it.more(); piece_it.next())
        {
            //DEBUG_P2("Piece %p %p ", piece_it.owner(), piece_it.parent());
            //printf("Piece %c\n", piece_it.owner()->name);
        
            for (PPChain::Iterator placement_it(piece_it.owner()->placements); placement_it.more(); placement_it.next())
            {
                if (!placement_it.owner()->accepted)
                {
                    //DEBUG_("start accept\n");
                    placement_it.owner()->accept();
                    
                    bool zero_placements = false;
                    bool one_placement = false;
                    
                    for (CellChain::Iterator cell_it(all_cells); cell_it.more(); cell_it.next())
                        if (cell_it.owner()->nr_piece_placements == 0)
                        {
                            zero_placements = true;
                            break;
                        }
                        else if (cell_it.owner()->nr_piece_placements == 1)
                            one_placement = true;
        
                    //DEBUG_("start undo_accept\n");
                    placement_it.owner()->undo_accept();
                    
                    if (zero_placements)
                    {
                        placement_it.owner()->remove();
                        placement_it.owner()->next_removed = removed;
                        removed = placement_it.owner();
                        go = true;
                    }
        
                    //DEBUG_(zero_placements ? "*" : one_placement ? "1" : "_");
                    
                    //return 0;
                }
            }
            
            if (piece_it.owner()->placements.isEmpty())
            {
                //printf("***Break1\n");

                // Restore piece placements that where removed before.
                for (; removed; removed = removed->next_removed)
                {
                    removed->undo_remove();
                }
                
                depth--;
                return;
            }
        }

        // For all pieces
        for (PieceChain::Iterator piece_it(all_pieces); piece_it.more(); piece_it.next())
        {
            Piece* piece = piece_it.owner();
            int nr_sel_placements = piece->nr_sel_placements;
            
            //printf("Piece %c: %d\n", piece->name, piece->nr_sel_placements);
            
            // Determine the groups of connected selected placements
            if (nr_sel_placements > 0 && nr_sel_placements < plurality)
            {
                int groups[plurality];
                for (int i = 0; i < plurality; i++)
                    groups[i] = i;
                
                for (int i = 0; i < nr_sel_placements-1; i++)
                    for (int j = 0; j < nr_sel_placements; j++)
                        if (groups[i] != groups[j] && neighbours(piece->sel_placements[i], piece->sel_placements[j]))
                        {
                            for (int k = i+1; k < nr_sel_placements; k++)
                                if (groups[k] == groups[j])
                                    groups[k] = groups[i];
                        }
            
                //for (int i = 0; i < nr_sel_placements; i++)
                //    printf("groups[%d] = %d\n", i, groups[i]);
                    
                // Mark all placements as possible (excluding those that have already been accepted)
                for (PPChain::Iterator placement_it(piece_it.owner()->placements); placement_it.more(); placement_it.next())
                {
                    //print(placement_it.owner());
                    placement_it.owner()->possible = !placement_it.owner()->accepted;
                }
                //printf("\n");
                
                // For each group, determine the possible placements
                for (int i = 0; i < nr_sel_placements; i++)
                    if (groups[i] == i)
                    {
                        //printf("process group %d\n", i);
                        
                        // Reset distances of all possible placements
                        for (PPChain::Iterator placement_it(piece_it.owner()->placements); placement_it.more(); placement_it.next())
                            placement_it.owner()->possible_at = 0;
                        
                        // Reset counters of number of placements that cover a certain cell
                        for (CellChain::Iterator cell_it(all_cells); cell_it.more(); cell_it.next())
                            cell_it.owner()->covered_by_placement = 0;

                        int nr_placements_found = 0;
                        PiecePlacement* piece_placement_found = 0;                        
                        for (int j = i; j < nr_sel_placements; j++)
                            if (groups[j] == i)
                            {
                                //printf("%d, %d:", j, nr_sel_placements);
                                for (PiecePlacementNeighbour::Iterator placement_it(piece->sel_placements[j]->neighbours); placement_it.more(); placement_it.next())
                                {
                                    PiecePlacement* placement = placement_it.value();
                                    if (placement->possible)
                                    {
                                        placement->possible_at = nr_sel_placements;
                                        //print(placement);
                                        
                                        nr_placements_found++;
                                        piece_placement_found = placement;
                                        // for all cells in this placement, increment covered_by_placement
                                        for (PiecePlacementUseCell::CellsIterator cell_it(placement->cells); cell_it.more(); cell_it.next())
                                            cell_it.cell()->covered_by_placement++;
                                    }
                                }
                                //printf("\n");
                            }
                        
                        // See if there are cells that are covered by all of the placements found
                        for (CellChain::Iterator cell_it(all_cells); cell_it.more(); cell_it.next())
                            if (cell_it.owner()->covered_by_placement == nr_placements_found)
                            {
                                // Remove all placements of other pieces
                                for (PiecePlacementUseCell::PiecePlacementIterator pp_it(cell_it.owner()->piece_placements); pp_it.more(); pp_it.next())
                                {    
                                    PiecePlacement* placement = pp_it.piecePlacement();
                                    if (placement->chain.parent != piece)
                                    {
                                        placement->remove();
                                        placement->next_removed = removed;
                                        removed = placement;
                                        //print(placement_it.owner());
                                        go = true;
                                    }
                                }
                            }
                            
                        if (piece_placement_found != 0 && (difficult_piece == 0 || nr_placements_found < difficult_piece_nr_placements))
                        {
                            difficult_piece = piece;
                            difficult_piece_placement = piece_placement_found;
                            difficult_piece_nr_placements = nr_placements_found;
                        }
                            
                        for (int k = nr_sel_placements; k < plurality-1; k++)
                        {
                            for (PPChain::Iterator placement_it(piece->placements); placement_it.more(); placement_it.next())
                            {
                                PiecePlacement* placement = placement_it.owner();
                                if (placement->possible_at == k)
                                {
                                    //print(placement);
                                    //printf(", %d:", k+1);
                                    for (PiecePlacementNeighbour::Iterator placement_it2(placement->neighbours); placement_it2.more(); placement_it2.next())
                                    {
                                        PiecePlacement* placement2 = placement_it2.value();
                                        if (placement2->possible && placement2->possible_at == 0)
                                        {
                                            placement2->possible_at = k+1;
                                            //print(placement2);
                                        }
                                    }
                                    //printf("\n");
                                }
                            }
                        }
                        
                        // Determine still possible placements
                        //printf("impossible:");
                        for (PPChain::Iterator placement_it(piece_it.owner()->placements); placement_it.more(); placement_it.next())
                            if (placement_it.owner()->possible && placement_it.owner()->possible_at == 0)
                            {
                                placement_it.owner()->possible = false;
                                //print(placement_it.owner());
                            }
                        //printf("\n");
                    }
                
                // Remove all impossible placements (and reset all parameters)
                //printf("removed:");
                for (PPChain::Iterator placement_it(piece_it.owner()->placements); placement_it.more(); placement_it.next())
                {
                    if (!placement_it.owner()->possible)
                    {
                        placement_it.owner()->remove();
                        placement_it.owner()->next_removed = removed;
                        removed = placement_it.owner();
                        //print(placement_it.owner());
                        go = true;
                    }
                    
                    placement_it.owner()->possible = false;
                    placement_it.owner()->possible_at = 0;
                }
                //printf("\n");

                if (piece_it.owner()->placements.isEmpty())
                {
                    //printf("***Break2\n");

                    // Restore piece placements that where removed before.
                    for (; removed; removed = removed->next_removed)
                    {
                        removed->undo_remove();
                    }
                    
                    depth--;
                    return;
                }
            }
        }
                
        //DEBUG_("\n");
    }

    // Find the cell with the least number of placements left
    Cell* cell = 0;
    int min_nr_piece_placements = 0;
    for (CellChain::Iterator cell_it(all_cells); cell_it.more(); cell_it.next())
    {
        if (cell == 0 || cell_it.owner()->nr_piece_placements < min_nr_piece_placements)
        {
            cell = cell_it.owner();
            min_nr_piece_placements = cell->nr_piece_placements;
        }
        //fprintf(f, "Cell %d: %d\n", cell_it.owner()->nr, cell_it.owner()->nr_piece_placements);
    }
    
    if (cell == 0)
    {
        //static int c = 0;
        //printf("sol %d\n", ++c);
        print_solution(stdout);
        //printf("None-found\n");
    }
    else if (min_nr_piece_placements == 1 || difficult_piece == 0)
    {
        for (PiecePlacementUseCell::PiecePlacementIterator piece_placement_it(cell->piece_placements); piece_placement_it.more(); piece_placement_it.next())
        {
            PiecePlacement* piece_placement = piece_placement_it.piecePlacement();
            piece_placement->accept();

            solve();
                        
            piece_placement->undo_accept();
        }
    }
    else
    {
        difficult_piece_placement->accept();

        solve();
                    
        difficult_piece_placement->undo_accept();
        
        difficult_piece_placement->remove();
        difficult_piece_placement->next_removed = removed;
        removed = difficult_piece_placement;
        
        depth--;
        
        solve();
        
        depth++;
    }
    
    // Restore piece placements that where removed before.
    for (; removed; removed = removed->next_removed)
    {
        removed->undo_remove();
    }
    
    depth--;
}

int main(int argc, char *argv[])
{
    FILE* f = fopen("dpfp_CWP_15_7.txt","rt");
    //FILE* f = fopen("dpfp_CWP_3_10.txt","rt");
    if (f == 0)
        return 1;
    read_puzzle(f);
    fclose(f);

    find_neighbours();

    f = fopen("out1.txt", "wt");
    print_state(f);
    fclose(f);
        
    solve();    

    DEBUG_("DONE\n");
    return 0;
}