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


#define MAX_PLURALITY 5

const char* at_debug = "";

class UndoContext;
class Undoable
{
    friend class UndoContext;
public:
    Undoable() : _in(false) {}
    void addToUndoContext()
    {
        _prev_undoable = _undoable;
        _in = true;
        _undoable = this;
    }
    virtual void undo() = 0;
private:
    static void undo_till(Undoable *till)
    {
        while (_undoable != till)
        {
            _undoable->undo();
            _undoable->_in = false;
            _undoable = _undoable->_prev_undoable;
        }
    }
    static Undoable* _undoable;
    Undoable *_prev_undoable;
    bool _in;
};
Undoable *Undoable::_undoable = 0;

class UndoContext
{
public:
    UndoContext() : _till(Undoable::_undoable) {}
    ~UndoContext() { Undoable::undo_till(_till); }
private:
    Undoable* _till;
};

template <class T, class S>
class Chain : public Undoable
{
public:
    Chain(T* n_owner = 0, S* n_parent = 0) : next(this), prev(this), owner(n_owner), parent(n_parent) {}
    bool isEmpty() { return next == this; }
    void push_back(Chain<T,S>* chain)
    {
        chain->prev = prev;
        prev->next = chain;
        prev = chain;
        chain->next = this;
    }
    bool empty() { return next == this; }
    int size()
    {
        int result = 0;
        for (Chain<T,S>* it = next; it != this; it = it->next)
            result++;
        return result;
    }
    void remove()
    {
        next->prev = prev;
        prev->next = next;

        Undoable::addToUndoContext();
    }
    virtual void undo()
    {
        next->prev = this;
        prev->next = this;
    }
    
    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;
    };
    
    Chain<T,S>* next;
    Chain<T,S>* prev;
    T* owner;
    S* parent;
};

    
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();
    }

    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;
        }
        Neighbour* cur() { return _cur->owner; }
        void remove() { _cur->owner->remove(_cur); }
    private:
        NChain* _end;
        NChain* _cur;
    };

    NChain chain1;
    NChain chain2;
    
    virtual void dummy() {}
};

class PiecePlacement;
class PiecePlacementNeighbour : public Neighbour<PiecePlacement>
{
public:
    PiecePlacementNeighbour(PiecePlacement* e1, NChain& c1, PiecePlacement* e2, NChain& c2, int touching_val)
      : Neighbour<PiecePlacement>(e1, c1, e2, c2), touching(touching_val) {}
    int touching;
};
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();
    virtual void undo();
};

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; }
        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(); }
    private:
        CAPPChain* _end;
        CAPPChain* _cur;
    };

    class PiecePlacementIterator
    {
    public:
        PiecePlacementIterator(PPUCChain& chain) { _end = &chain; _cur = chain.next; }
        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(); }
    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();
    parent->nr_piece_placements--;
}
void PPUCChain::undo()
{
    PPUCChainBase::undo();
    parent->nr_piece_placements++;
}

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

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[MAX_PLURALITY];
    
    void remove();
        
    PieceChain chain;
    
    int nr_forced_placements;
};

class PiecePlacement : Undoable
{
public:
    PiecePlacement(Piece* piece) : chain(this, piece), accepted(false), removed(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)
    {
        removed = true;

        addToUndoContext();

        // 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(); // -- for resetting removed flag
    }
    
    void accept()
    {
        addToUndoContext();

        // 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;
    }
    
    virtual void undo()
    {
        if (accepted)
        {
            chain.parent->remove_selected(this);
    
            // 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 = 0;
            }
            
            accepted = false;
        }
        if (removed)
            removed = false;
    }

    int nr;
    int dist;
    int dists[MAX_PLURALITY];
    
    PPNChain neighbours;
    CAPPChain cells;
    
    PPChain chain;
    
    bool accepted;
    bool removed;
    
    bool possible;
    int possible_at;
};


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();
}

class PiecePlacements
{
public:
    PiecePlacements() : _elems(0) {}
    ~PiecePlacements()
    {
        delete _elems;
    }
    void transferTo(PiecePlacements &target)
    {
        delete target._elems;
        target._elems = _elems;
        _elems = 0;
    }
    void add(PiecePlacement* placement)
    {
        _elems = new Element(placement, _elems);
    }
private:
    struct Element
    {
        Element(PiecePlacement* v, Element* n) : value(v), next(n) {}
        ~Element() { delete next; }
        PiecePlacement* value;
        Element* next;
    };
public:
    class Iterator
    {
    public:
        Iterator(PiecePlacements &piecePlacements) : _it(piecePlacements._elems) {}
        bool more() { return _it != 0; }
        void next() { _it = _it->next; }
        PiecePlacement* value() { return _it->value; }
    private:
        Element* _it;
    };
private:
    Element* _elems;
};

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

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);

    cells = new Cell[nr_cells];
    for (int i = 0; i < nr_cells; i++)
    {
        cells[i].nr = i;
        all_cells.push_back(&cells[i].chain);
    }
        
    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);
    }

    for (int p = 0; p < nr_pieces; p++)
    {
        int nr_placements;
        fscanf(fin, "%d", &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);

            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;
                }
                
                placement->addCell(&cells[lnr]);
            }
        }
    }
    
    int nr_neighbours = 0;
    fscanf(fin, "%d", &nr_neighbours);
    if (nr_neighbours == 0)
    {
        printf("Error: Neighbour definition missing. (Run gen_dpfp with -n option)\n");
        exit(1);
    }
    
    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;
                int touching = 0;
                
                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)
                        {
                            for (CellNeighbour::Iterator neighbour(cell1->neighbours); neighbour.more(); neighbour.next())
                                if (neighbour.value() == cell2)
                                {
                                    touching++;
                                    break;
                                }
                        }
                    }
                }
                if (!overlap && touching > 0)
                {
                    nr++;
                    makeNeighbours(placement1.owner(), placement2.owner(), touching);
                }
            }
        }
    }
}

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);
    }
}

int total_touching = 0;
int max_total_touching = 100000;

int sq_n;
int sq_m;
#define CELL(X,Y) cells[(X)*sq_m + (Y)]

void print_solution(FILE* f)
{
    fprintf(f, "p(\"");
    for (int i = 0; i < sq_n; i++)
    {
        for (int j = 0; j < sq_m; j++)
            fprintf(f, "%c", CELL(i,j).accepted_placement->chain.parent->name);
    }
    fprintf(f, "\") // %d\n", total_touching);
    fflush(f);
}

void print_visual_solution(FILE* f)
{
    for (int j = 0; j < sq_m; j++)
        fprintf(f, "+-");
    fprintf(f, "+\n");
        
    for (int i = 0; i < sq_n; i++)
    {
        fprintf(f, "|%c", CELL(i,0).accepted_placement != 0 ? CELL(i,0).accepted_placement->chain.parent->name : ' ');
        for (int j = 0; j < sq_m-1; j++)
            fprintf(f, "%c%c", CELL(i,j).accepted_placement != 0 && CELL(i,j).accepted_placement == CELL(i,j+1).accepted_placement ? CELL(i,j).accepted_placement->chain.parent->name : '|',
                        CELL(i,j+1).accepted_placement != 0 ? CELL(i,j+1).accepted_placement->chain.parent->name : ' ');
        fprintf(f, "|\n");

        if (i < sq_n-1)
        {
            for (int j = 0; j < sq_m; j++)
                fprintf(f, "|%c", CELL(i,j).accepted_placement != 0 && CELL(i,j).accepted_placement == CELL(i+1,j).accepted_placement ? CELL(i,j).accepted_placement->chain.parent->name : '-');
            fprintf(f, "+\n");
        }
    }
    for (int j = 0; j < sq_m; j++)
        fprintf(f, "+-");
    fprintf(f, "+\n\n");
}

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;
}

int neighboursTouching(PiecePlacement* a, PiecePlacement* b)
{
    for (PiecePlacementNeighbour::Iterator placement_it(a->neighbours); placement_it.more(); placement_it.next())
        if (placement_it.value() == b)
            return dynamic_cast<PiecePlacementNeighbour*>(placement_it.cur())->touching;
            
    return 0;
}

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++;
    }
}

bool exclude_cycle = false;
bool exclude_tree = false;


void remove_impossible()
{
    bool go = true;
    while (go)
    {
        go = false;
            
        for (PieceChain::Iterator piece_it(all_pieces); piece_it.more(); piece_it.next())
        {
            Piece* piece = piece_it.owner();
        
            for (PPChain::Iterator placement_it(piece_it.owner()->placements); placement_it.more(); placement_it.next())
            {
                if (!placement_it.owner()->accepted)
                {
                    int old_total_touching = total_touching;
                    bool zero_placements = false;
                    bool one_placement = false;
                        
                    {
                        UndoContext acceptContext;
                        placement_it.owner()->accept();
                        
                        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;
                    }
                                    
                    if (zero_placements) // || !okay
                    {
                        placement_it.owner()->remove();
                        go = true;
                    }
        
                    total_touching = old_total_touching;
                }
            }
        }
    }
}

void solve()
{
    if (0)
    {
        static int cc = 0;
        cc++;
        if (cc > 10000)
            exit(0);
    }
    
    if (all_cells.empty())
    {
        print_solution(stdout);
        return;
    }
    
    // Reset status for pieces
    for (PieceChain::Iterator piece_it(all_pieces); piece_it.more(); piece_it.next())
    {
        Piece* piece = piece_it.owner();
        piece->nr_forced_placements = 0;
        
        // If a piece has no placements and not all selected, exit.
        if (piece->placements.empty() && !piece->all_selected())
        {
            return;
        }
    }

    UndoContext removedPiecePlacementsContext;

    // See if there are cells with zero or one placements. Repeat when placements have been removed
    int max_nr_forced_placements = 0;
    Piece* piece_with_max_forced_placements = 0;
    Cell* cell_with_min_nr_placement = 0;
    int min_nr_placements;
    bool go = true;
    while (go)
    {
        go = false;
        // Exit if there is a cell with no placement
        for (CellChain::Iterator cell_it(all_cells); cell_it.more(); cell_it.next())
            if (cell_it.owner()->nr_piece_placements == 0)
            {
                return;
            }
        
        // Check cells with one placement
        for (CellChain::Iterator cell_it(all_cells); cell_it.more(); cell_it.next())
        {
            Cell* cell = cell_it.owner();
            if (cell->nr_piece_placements == 1)
            {
                PiecePlacementUseCell::PiecePlacementIterator pp_it(cell->piece_placements);
                PiecePlacement* piece_placement = pp_it.piecePlacement();
                Piece* piece = piece_placement->chain.parent;
                if (piece->nr_sel_placements == 0)
                {
                    // Immediately start with this piece
                    piece_placement->accept();
                    solve();
                    return;
                }
                if (++piece->nr_forced_placements > max_nr_forced_placements)
                {
                    max_nr_forced_placements = piece->nr_forced_placements;
                    piece_with_max_forced_placements = piece;
                }
            }
            if (cell_with_min_nr_placement == 0 || cell->nr_piece_placements < min_nr_placements)
            {
                cell_with_min_nr_placement = cell;
                min_nr_placements = cell->nr_piece_placements;
            }
        }
    }
        
    if (1)
    {
        static clock_t ct = clock();
        if (ct < clock())
        {
            ct = clock() + 6000;
            print_visual_solution(stderr);
        }
    }

    // Check if piece with some placements and no continuation.
    Piece *piece_with_min_nr_placements = 0;
    for (PieceChain::Iterator piece_it(all_pieces); piece_it.more(); piece_it.next())
    {
        Piece* piece = piece_it.owner();
        
        if (piece->nr_sel_placements > 0 && !piece->all_selected())
        {
            // Find neighbours of pieces that still need placements
            int nr_placements = 0;
            for (PPChain::Iterator placement_it(piece->placements); placement_it.more(); placement_it.next())
            {
                PiecePlacement* piece_placement = placement_it.owner();
                if (!piece_placement->accepted)
                {
                    // piece_placement has not been accepted yet. See if it is a neighbour of a
                    // piece placement that has been accepted
                    for (PiecePlacementNeighbour::Iterator placement_it(piece_placement->neighbours); placement_it.more(); placement_it.next())
                        if (placement_it.value()->accepted)
                        {
                            nr_placements++;
                            break;
                        }
                }
            }
            if (nr_placements == 0)
            {
                return;
            }
            if (piece_with_min_nr_placements == 0 || nr_placements < min_nr_placements)
            {
                min_nr_placements = nr_placements;
                piece_with_min_nr_placements = piece;
            }
        }
    }
    
    Piece *selected_piece = 0;
    if (min_nr_placements == 1)
        selected_piece = piece_with_min_nr_placements;
    else if (piece_with_max_forced_placements != 0)
        selected_piece = piece_with_max_forced_placements;
    else
    {
        int min_nr;
        for (PiecePlacementUseCell::PiecePlacementIterator pp_it(cell_with_min_nr_placement->piece_placements); pp_it.more(); pp_it.next())
        {
            PiecePlacement* piece_placement = pp_it.piecePlacement();
            Piece* piece = piece_placement->chain.parent;
            if (piece->nr_sel_placements == 0 && selected_piece != piece)
            {
                int nr = piece->placements.size();
                if (selected_piece != 0 && nr < min_nr)
                {
                    min_nr = nr;
                    selected_piece = piece;
                }
            }
        }
        if (selected_piece != 0)
        {
            // first try placements at the cell with min nr placements
            for (PiecePlacementUseCell::PiecePlacementIterator pp_it(cell_with_min_nr_placement->piece_placements); pp_it.more(); pp_it.next())
            {
                PiecePlacement* piece_placement = pp_it.piecePlacement();
                if (piece_placement->chain.parent == selected_piece)
                {
                    {
                        UndoContext acceptPiecePlacement;
                        piece_placement->accept();
                        solve();
                    }
                    piece_placement->remove();
                }
            }
        }
        else
        {
            int min_nr;
            for (PieceChain::Iterator piece_it(all_pieces); piece_it.more(); piece_it.next())
            {
                Piece* piece = piece_it.owner();
                
                if (piece->nr_sel_placements == 0)
                {
                    int nr = piece->placements.size();
                    if (selected_piece == 0 || nr < min_nr)
                    {
                        min_nr = nr;
                        selected_piece = piece;
                    }
                }
            }
        }
        if (selected_piece == 0)
            selected_piece = piece_with_min_nr_placements;
    }


    for (PPChain::Iterator placement_it(selected_piece->placements); placement_it.more(); placement_it.next())
    {
        // skip accepted piece placements
        PiecePlacement* piece_placement = placement_it.owner();
        if (piece_placement->accepted)
            continue;
        
        bool placement_possible = selected_piece->nr_sel_placements == 0;
        if (!placement_possible)
        {
            // check if placement has an accepted neighbour
            for (PiecePlacementNeighbour::Iterator placement_it(piece_placement->neighbours); placement_it.more(); placement_it.next())
            {
                PiecePlacement* placement = placement_it.value();
                if (placement->accepted)
                {
                    placement_possible = true;
                    break;
                }
            }
        }
            
        if (placement_possible)
        {
            {
                UndoContext acceptPiecePlacement;
                piece_placement->accept();
                solve();
            }
            piece_placement->remove();
        }
    }
}

void solve_by_grid(Piece* last_piece)
{
    {
        static clock_t ct = 0;
        if (ct < clock())
        {
            ct = clock() + 1000;
            print_visual_solution(stderr);
        }
    }

    if (last_piece != 0 && last_piece->nr_sel_placements == plurality)
    {
        int nr_sel_placements = plurality;
        // check if all are connected
         int groups[MAX_PLURALITY];
        for (int i = 0; i < nr_sel_placements; i++)
            groups[i] = i;
    
        for (int j = 1; j < nr_sel_placements; j++)
            for (int i = 0; i < j; i++)
                if (groups[i] != groups[j] && neighboursTouching(last_piece->sel_placements[i], last_piece->sel_placements[j]) > 0)
                {
                    int groupsi = groups[i];
                    int groupsj = groups[j];
                    if (groupsj < groupsi) { int t = groupsj; groupsj = groupsi; groupsi = t; }
                    for (int k = 0; k < nr_sel_placements; k++)
                        if (groups[k] == groupsj)
                            groups[k] = groupsi;
                }
        // normalize
        int map[MAX_PLURALITY];
        for (int i = 0; i < nr_sel_placements; i++)
            map[i] = -1;
        int nr_groups = 0;
        for (int i = 0; i < nr_sel_placements; i++)
            if (map[groups[i]] == -1)
                map[groups[i]] = nr_groups++;
        for (int i = 0; i < nr_sel_placements; i++)
            groups[i] = map[groups[i]];
        if (nr_groups > 1)
            return;
    }
    
        
     UndoContext removedPiecePlacementsContext;

    // First remove all pieces placements which cannot be placed, because they would make
    // it impossible for some cells to be covered.
    // This is an iterative process, because if a placement is impossible, this could
    // make other placements impossible as well.

    Piece* difficult_piece = 0;
    int difficult_piece_nr;
    PiecePlacements piece_placements_difficult_piece;

    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;
        if (nr_sel_placements > 0)
        {
            // Determine number of groups of connected piece placements for this piece
             int groups[MAX_PLURALITY];
            for (int i = 0; i < nr_sel_placements; i++)
                groups[i] = i;
        
            for (int j = 1; j < nr_sel_placements; j++)
                for (int i = 0; i < j; i++)
                    if (groups[i] != groups[j] && neighboursTouching(piece->sel_placements[i], piece->sel_placements[j]) > 0)
                    {
                        int groupsi = groups[i];
                        int groupsj = groups[j];
                        if (groupsj < groupsi) { int t = groupsj; groupsj = groupsi; groupsi = t; }
                        for (int k = 0; k < nr_sel_placements; k++)
                            if (groups[k] == groupsj)
                                groups[k] = groupsi;
                    }
            // normalize
            int map[MAX_PLURALITY];
            for (int i = 0; i < nr_sel_placements; i++)
                map[i] = -1;
            int nr_groups = 0;
            for (int i = 0; i < nr_sel_placements; i++)
                if (map[groups[i]] == -1)
                    map[groups[i]] = nr_groups++;
            for (int i = 0; i < nr_sel_placements; i++)
                groups[i] = map[groups[i]];
            int left = plurality - nr_sel_placements;
        
            // Initialize nrs for each group
            for (PPChain::Iterator placement_it(piece->placements); placement_it.more(); placement_it.next())
            {
                PiecePlacement* piece_placement = placement_it.owner();
                piece_placement->dist = 0;
                for (int group = 0; group < nr_groups; group++)
                    piece_placement->dists[group] = 0;
            }
            
            int nr_poss_piece_placements = 0;
            PiecePlacements poss_piece_placements;
            
            // Process by group
            for (int group = 0; group < nr_groups; group++)
            {
                for (int i = 0; i < nr_sel_placements; i++)
                    if (groups[i] == group)
                        for (PiecePlacementNeighbour::Iterator placement_it(piece->sel_placements[i]->neighbours); placement_it.more(); placement_it.next())
                        {
                            PiecePlacement* neighbour = placement_it.value();
                            if (!neighbour->accepted && neighbour->dists[group] == 0)
                            {
                                neighbour->dist = 1;
                                neighbour->dists[group] = 1;
                                nr_poss_piece_placements++;
                                poss_piece_placements.add(neighbour);
                            }
                        }
                for (int d = 1; d < left; d++)
                {
                    int d_n = d + 1;
                    for (PPChain::Iterator placement_it(piece->placements); placement_it.more(); placement_it.next())
                    {
                        PiecePlacement* piece_placement = placement_it.owner();
                        if (piece_placement->dists[group] == d)
                            for (PiecePlacementNeighbour::Iterator placement_it(piece_placement->neighbours); placement_it.more(); placement_it.next())
                            {
                                PiecePlacement* neighbour = placement_it.value();
                                if (!neighbour->accepted && neighbour->dists[group] == 0)
                                {
                                    neighbour->dists[group] = d_n;
                                    if (neighbour->dist == 0 || neighbour->dist > d_n)
                                        neighbour->dist = d_n;
                                }
                            }
                    }
                }
            }
            if (nr_poss_piece_placements == 0)
                return; // -- found a piece without possible placements
                
            if (difficult_piece == 0 || difficult_piece_nr > nr_poss_piece_placements)
            {
                difficult_piece = piece;
                difficult_piece_nr = nr_poss_piece_placements;
                poss_piece_placements.transferTo(piece_placements_difficult_piece);
            }
            
            // Remove unreachable piece placements
            for (PPChain::Iterator placement_it(piece_it.owner()->placements); placement_it.more(); placement_it.next())
            {
                PiecePlacement* piece_placement = placement_it.owner();
                if (!piece_placement->accepted && piece_placement->dist == 0)
                    piece_placement->remove();
            }
            
            if (nr_groups > 1)
            {
                // Check if groups can be connected
                 int congroups[MAX_PLURALITY];
                for (int i = 0; i < nr_groups; i++)
                    congroups[i] = i;

                int uncon_groups = nr_groups;

                for (PPChain::Iterator placement_it(piece_it.owner()->placements); placement_it.more(); placement_it.next())
                {
                    PiecePlacement* piece_placement = placement_it.owner();
                    if (piece_placement->dist != 0)
                    {
                        for (int j = 1; j < nr_groups; j++)
                            for (int i = 0; i < j; i++)
                                if (   congroups[i] != congroups[j] 
                                    && piece_placement->dists[i] != 0
                                    && piece_placement->dists[j] != 0
                                    && piece_placement->dists[i] + piece_placement->dists[j] <= left+1)
                                {
                                    uncon_groups--;
                                    int groupsi = congroups[i];
                                    int groupsj = congroups[j];
                                    if (groupsj < groupsi) { int t = groupsj; groupsj = groupsi; groupsi = t; }
                                    for (int k = 0; k <= nr_groups; k++)
                                        if (congroups[k] == groupsj)
                                            congroups[k] = groupsi;
                                }
                        if (uncon_groups == 1)
                            break;
                    }
                }
                if (uncon_groups > 1)
                    return; // -- some groups cannot be connected
            }
        }
    }
        
    if (all_cells.empty())
    {
        print_solution(stdout);
        return;
    }

    // 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;
        }
    }
    
    if (difficult_piece != 0 && difficult_piece_nr < min_nr_piece_placements)
    {
        for (PiecePlacements::Iterator placement_it(piece_placements_difficult_piece); placement_it.more(); placement_it.next())
        {
            PiecePlacement* piece_placement = placement_it.value();
            if (!piece_placement->removed)
            {
                {
                    UndoContext acceptPiecePlacement;
                    piece_placement->accept();
        
                    solve_by_grid(piece_placement->chain.parent);
                }
                piece_placement->remove();
            }
        }
    }
    else
    {
        for (PiecePlacementUseCell::PiecePlacementIterator piece_placement_it(cell->piece_placements); piece_placement_it.more(); piece_placement_it.next())
        {
            PiecePlacement* piece_placement = piece_placement_it.piecePlacement();
 
            UndoContext acceptPiecePlacement;
            piece_placement->accept();

            solve_by_grid(piece_placement->chain.parent);
        }
    }
}


void placePiece(int p1, int p2, int p3, int p4)
{
    for (PieceChain::Iterator piece(all_pieces); piece.more(); piece.next())
    {
        for (PPChain::Iterator placement(piece.owner()->placements); placement.more(); placement.next())
        {
            bool found_p1 = false;
            bool found_p2 = false;
            bool found_p3 = false;
            bool found_p4 = false;
            
            for (CAPPChain::Iterator cell(placement.owner()->cells); cell.more(); cell.next())
            {
                if (cell.owner()->pp_chain.parent->nr == p1)
                    found_p1 = true;
                else if (cell.owner()->pp_chain.parent->nr == p2)
                    found_p2 = true;
                else if (cell.owner()->pp_chain.parent->nr == p3)
                    found_p3 = true;
                else if (cell.owner()->pp_chain.parent->nr == p4)
                    found_p4 = true;
            }
            
            if (found_p1 && found_p2 && found_p3 && found_p4)
            {
                placement.owner()->accept();
                return;
            }
        }
    }
    
    printf("Did not find %d,%d,%d,%d\n", p1, p2, p3, p4);
}

//  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14
// 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
// 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
// 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
// 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74
// 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
// 90 91 92 93 94 95 96 97 98 99100101102103104

void problem1()
{
    placePiece( 0,  1,  2,  3);
    placePiece(15, 16, 17, 18);
    placePiece(30, 31, 32, 33);
    placePiece(45, 46, 47, 48);
    placePiece(60, 61, 62, 63);
    
    placePiece(28, 29, 43, 44);
    placePiece(56, 57, 71, 72);
    placePiece(58, 59, 73, 74); 
    placePiece(86, 87,101,102);
    placePiece(88, 89,103,104);
}

int main(int argc, char *argv[])
{
    if (argc != 4 || atoi(argv[1]) <= 0 || atoi(argv[2]) <= 0 || atoi(argv[3]) <= 0)
        exit(-1);
    sq_n = atoi(argv[2]);
    sq_m = atoi(argv[1]);
    plurality = atoi(argv[3]);
    FILE* f = stdin;

    if (f == 0)
    {
        printf("File not found\n");
        return 1;
    }
    read_puzzle(f);
    fclose(f);

    find_neighbours();

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

    clock_t start_t = clock();
    
    remove_impossible();

    solve_by_grid(0);    

    fprintf(stderr, "DONE in %ld\n", clock() - start_t);
    return 0;
}