Hokkaido Univ.& Hitachi 2nd New-concept Computing Contest 2017

#include <array>
#include <chrono>
#include <cstdlib>
#include <iostream>
#include <sstream>
#include <string>
#include <cassert>
#include <cmath>
#include <climits>
#include <cstdio>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <functional>
#include <numeric>
#include <iomanip>
#include <cstring>


using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair
#define mt make_tuple

int dx8[] = { 1, 1, 1, 0, -1, -1, -1, 0 };
int dy8[] = { 1, 0, -1, -1, -1, 0, 1, 1 };

// http://shindannin.hatenadiary.com/entry/20121224/1356364040
unsigned int myrand()
{
    static unsigned int x = 123456789, y = 362436069, z = 521288629, w = 88675123;
    unsigned int t;
    t = (x ^ (x << 11)); x = y; y = z; z = w;
    return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8))) % RAND_MAX;
}

struct Input {
    int srcV;
    int srcE;
    vector<tuple<int, int>> srcEdges;
    vector<char> srcEdgesMemo;    // 頂点間にエッジがあれば1
    vector<vector<int>> srcEdgesVec;

    int dstV;
    int dstE;
    int dstSize; // 辺の長さ

                 // u, vの順序関係は問わない
    bool hasSrcEdge(int u, int v) const {
        return srcEdgesMemo[u * srcV + v];
    }
};

struct Mapper
{
    // dst側の各頂点について、src側の頂点を保持
    vector<vector<short>> mapper;

    // 頂点別の要素数
    vector<short> count;

    // 異番号で隣り合う辺
    // e.g. adjacents[2][5] = 4 の場合、2と5は4箇所で隣り合っている
    vector<vector<short>> adjacents;

    // src側の各頂点について、dst側の存在場所
    vector<set<pair<short, short>>> xylist;

    // -1のままの場所
    set<pair<short, short>> emptylist;

    int m_size; // 盤面の縦幅・横幅
    int m_srcV;
    int m_potential = 0;

    Mapper() {}
    void init(Input& in) {
        mapper.resize(in.dstSize + 2, vector<short>(in.dstSize + 2, -1)); // 周囲1マス分に注意
        count.resize(in.srcV);
        adjacents.resize(in.srcV, vector<short>(in.srcV));
        xylist.resize(in.srcV);
        REP(y, in.dstSize) {
            REP(x, in.dstSize) {
                emptylist.insert(mp(x, y));
            }
        }
        m_size = in.dstSize;
        m_srcV = in.srcV;
    };

    int getPotential() {
        return m_potential;
    }

    int setV(int x, int y, short v, const Input& in) {
        int edgeDiff = 0;  // エッジ数の増減を記録

                           // 今現在の値が非-1の場合、いったん-1に戻す、と考える
        auto old = this->getV(x, y);
        if (old != -1) {
            --count[old];
            // 隣り合ってる頂点との関係をリセット
            REP(d, 8) {
                auto x2 = x + dx8[d];
                auto y2 = y + dy8[d];
                auto nei = this->getV(x2, y2);
                if (old != nei && nei != -1) {
                    auto mn = min(nei, old);
                    auto mx = max(nei, old);
                    --adjacents[mn][mx];
                    if (adjacents[mn][mx] == 0) {
                        --m_potential;
                        if (in.hasSrcEdge(mn, mx)) {
                            --edgeDiff;
                        }
                    }
                }
            }
            xylist[old].erase(mp(x, y));
            emptylist.insert(mp(x, y));
        }

        // 隣り合ってる頂点との関係を加算
        mapper[y + 1][x + 1] = v;
        if (v != -1) {
            ++count[v];
            REP(d, 8) {
                auto x2 = x + dx8[d];
                auto y2 = y + dy8[d];
                auto nei = this->getV(x2, y2);
                if (v != nei && nei != -1) {
                    auto mn = min(nei, v);
                    auto mx = max(nei, v);
                    ++adjacents[mn][mx];
                    if (adjacents[mn][mx] == 1) {
                        m_potential++;
                        if (in.hasSrcEdge(mn, mx)) {
                            ++edgeDiff;
                        }
                    }
                }
            }
            xylist[v].insert(mp(x, y));
            emptylist.erase(mp(x, y));
        }

        return edgeDiff;
    }
    short getV(int x, int y) const {
        return mapper[y + 1][x + 1];
    }
    bool inRange(int x, int y) const {
        return 0 <= x && x < m_size && 0 <= y && y < m_size;
    }

    // (x, y)にある頂点を-1に戻したとして、連続性が途切れるかどうかを調べる
    // 簡易的に周囲8頂点を見て、連続していない飛び地があれば、連続性が途切れると判断
    bool canDelete(int x, int y) {
        auto old = this->getV(x, y);

        // 数が1個, 2個のときは周囲を調べずとも分かる
        if (count[old] == 1) return false;
        if (count[old] == 2) return true;

        // 8方向の値を取得
        string neighs = "";
        REP(d, 8) {
            auto x2 = x + dx8[d];
            auto y2 = y + dy8[d];
            auto v = (this->getV(x2, y2) == old) ? 'o' : 'x';
            if (d == 0) neighs = v;
            else {
                if (neighs.back() != v) neighs.push_back(v);
            }
        }
        // 許されるパターンは、"o" "ox" "xo" "oxo" "xox" だけ
        return (neighs == "o"
            || neighs == "ox"
            || neighs == "xo"
            || neighs == "oxo"
            || neighs == "xox"
            );
    }
};

struct Timer {
    std::chrono::time_point<std::chrono::system_clock> m_start;
    void start() {
        m_start = std::chrono::system_clock::now();
    }
    ll milli() {
        auto now = std::chrono::system_clock::now();
        auto diff = now - m_start;
        return std::chrono::duration_cast<std::chrono::milliseconds>(diff).count();
    }
};

struct Solver
{
    Input in;
    Mapper ans;
    std::chrono::time_point<std::chrono::system_clock> startTime;
    int m_prevAdd = -1;
    int m_prevLoss = -1;
    int m_prevBonus = -1;
    int m_prevEdgeNum = -1;
    const int MAX_TIME1 = 25000;
    const int MAX_TIME2 = 29940;
    Timer m_timer;

    void start()
    {
        m_timer.start();
    }

    ll getEllapsedTime()
    {
        return m_timer.milli();
    }

    void readInput()
    {
        cin >> in.srcV >> in.srcE;

        in.srcEdgesMemo.resize(in.srcV * in.srcV);
        in.srcEdgesVec.resize(in.srcV);

        REP(e, in.srcE) {
            int u, v;
            cin >> u >> v;
            --u; --v;
            in.srcEdges.pb(mt(u, v));
            in.srcEdgesMemo[u * in.srcV + v] = 1;
            in.srcEdgesMemo[v * in.srcV + u] = 1;
            in.srcEdgesVec[u].push_back(v);
            in.srcEdgesVec[v].push_back(u);
        }

        cin >> in.dstV >> in.dstE;

        REP(e, in.dstE) {
            int a, b;
            cin >> a >> b;
        }
        in.dstSize = int(round(sqrt(in.dstV)));

        // 次数のヒストグラム作成
        map<int, int> histo;
        int mx = 0;
        REP(v, in.srcV) {
            auto degree = SIZE(in.srcEdgesVec[v]);
            ++histo[degree];
            mx = max(mx, degree);
        }
        cerr << "input graph degree histogpram" << endl;
        REP(i, mx) {
            cerr << i << "\t" << histo[i] << endl;
        }

    }

    int getSrcSize(int v)
    {
        int n = 1;
        while (true) {
            if (n * n >= v) return n;
            ++n;
        }
    }

    void debugPrintMapper(Mapper& mapper)
    {
        REP(y, in.dstSize) {
            REP(x, in.dstSize) {
                cerr << mapper.getV(x, y) << "\t";
            }
            cerr << endl;
        }
        cerr << calcScore(mapper) << endl;

        // 得点となりうる頂点はいくつあるのか数える 多いほど得点の可能性が高い
        cerr << "edge potential sum = " << mapper.getPotential() << endl;

        // 各頂点について、エッジの状況を可視化
        map<int, int> potentialHisto;
        int maxPotential = 0;
        REP(v, in.srcV) {
            auto full = SIZE(in.srcEdgesVec[v]);

            auto adj = 0; // 得点を生み出しているエッジ数
            for (auto u : in.srcEdgesVec[v]) {
                auto mn = min(u, v);
                auto mx = max(u, v);
                if (mapper.adjacents[mn][mx] > 0) {
                    ++adj;
                }
            }

            auto potential = 0; // 隣り合う他者の異なり数
            REP(u, in.srcV) {
                if (u == v) continue;
                auto mn = min(u, v);
                auto mx = max(u, v);
                if (mapper.adjacents[mn][mx] > 0) {
                    ++potential;
                }
            }
            ++potentialHisto[potential];
            maxPotential = max(maxPotential, potential);

            //cerr << "    v" << v << ": " << " score " << adj << " / bestPotential " << bestPotential << " / full " << full << endl;
        }

        // 頂点のポテンシャル
        cerr << "potential histogram" << endl;
        REP(i, maxPotential + 1) {
            cerr << i << "\t" << potentialHisto[i] << endl;
        }

        cerr << endl;
    }

    // TODO: もっと賢く埋める
    void makeInitialMapperWithRandomLine(Mapper &ret, int vStart)
    {
        // まだ埋まっていないセルの数で長さを決める
        int locPerV = SIZE(ret.emptylist) / (in.srcV - vStart);

        vector<short> vs;

        for (auto v = vStart; v < in.srcV; ++v) {
            // 最初の座標を決める
            auto xy = *ret.emptylist.begin();
            auto x = xy.first;
            auto y = xy.second;
            assert(ret.getV(x, y) == -1);
            ret.setV(x, y, v, in);

            // 周囲にランダムに伸ばしていく
            int d = myrand() % 8;
            REP(i, locPerV - 1) {

                bool ok = false;
                REP(d2, 8) {
                    auto x2 = x + dx8[(d + d2) % 8];
                    auto y2 = y + dy8[(d + d2) % 8];

                    auto u = ret.getV(x2, y2);

                    // 画面外に行く場合はskip
                    if (x2 < 0 || x2 >= in.dstSize || y2 < 0 || y2 >= in.dstSize)
                        continue;

                    if (u == -1) {
                        ret.setV(x2, y2, v, in);
                        x = x2;
                        y = y2;
                        ok = true;
                        break;
                    }
                }

                if (!ok) break;
            }
            //debugPrintMapper(ret);
        }
    }

    // 各点ができるだけ直線に並ぶようにランダムに配置
    Mapper makeInitialMapper()
    {
        Mapper ret;
        ret.init(in);

        makeInitialMapperWithRandomLine(ret, 0);

        return ret;
    }


    // 座標xInit, yInitから長さsizeの斜め線を取れるだけ取る
    void setDiagonalLine(const int size, const int xInit, const int yInit, const int dx, const int dy, int &v, Mapper& mapper) {
        // 長さを得る
        int x = xInit;
        int y = yInit;
        int len = 0;
        while (true) {
            if (mapper.inRange(x, y)) {
                x += dx; y += dy; ++len;
            }
            else break;
        }
        auto lineNum = len / size;


        // 次にとれるだけとる
        x = xInit;
        y = yInit;

        // もし端数があるならその分スキップする
        REP(i, (len - lineNum * size) / 2) {
            x += dx; y += dy;
        }

        REP(i, lineNum) {
            REP(j, size) {
                if (v == in.srcV) return;
                mapper.setV(x, y, v, in);
                x += dx; y += dy;
            }
            ++v;
        }
        return;
    }

    Mapper makeInitialMapperDiagonalSub(const int size) {
        Mapper ret;
        ret.init(in);

        // 左上から右下に伸びる線
        int v = 0;
        int yInit = 0;
        int xInit = 0;
        while (yInit <= in.dstSize) {
            setDiagonalLine(size, xInit, yInit, 1, 1, v, ret);
            yInit += 2;
        }

        yInit = 0;
        xInit = 2;
        while (xInit <= in.dstSize) {
            setDiagonalLine(size, xInit, yInit, 1, 1, v, ret);
            xInit += 2;
        }

        // 右上から左下に伸びる線
        yInit = 0;
        xInit = 1;
        while (xInit <= in.dstSize) {
            setDiagonalLine(size, xInit, yInit, -1, 1, v, ret);
            xInit += 2;
        }

        yInit = (in.dstSize % 2) ? 1 : 2;
        xInit = in.dstSize - 1;
        while (yInit <= in.dstSize) {
            setDiagonalLine(size, xInit, yInit, -1, 1, v, ret);
            yInit += 2;
        }

        // 残りを埋める
        if (v != in.srcV) {
            makeInitialMapperWithRandomLine(ret, v);
        }

        return ret;
    }

    Mapper makeInitialMapperDiagonal() {
        Mapper ret;

        int locPerV = in.dstV / in.srcV;
        if (locPerV == 1) return makeInitialMapper();

        // あらゆるサイズを試す
        // TODO: 処理時間大丈夫か？
        int bestPotential = 0;
        FOR(size, 2, locPerV + 1) {
            Mapper candidate = makeInitialMapperDiagonalSub(size);
            //cerr << "---" << endl;
            //cerr << "bestsize, bestpotential = " << size << ", " << bestPotential << endl;
            //debugPrintMapper(candidate);

            auto curPotential = candidate.getPotential();
            if (curPotential > bestPotential) {
                ret = candidate;
                bestPotential = curPotential;
            }
        }
        return ret;
    }


    // 規則正しい初期盤面を作成
    // サイズ2の場合
    //    abcd
    //    badc
    //    abcd
    //    badc
    Mapper makeInitialMapperNxN() {
        Mapper ret;
        ret.init(in);

        int locPerV = in.dstV / in.srcV;

        if (locPerV == 1) return makeInitialMapper();

        auto squareSize = getSrcSize(in.srcV / 2);
        auto offset = (in.dstSize - squareSize * 2) / 2;

        bool flip = true;
        //int y = offset;
        int y = 0;
        //int x = offset;
        int v = 0;
        while (true) {
            // 縦が足りなければ終了
            if (y + locPerV - 1 >= in.dstSize) break;

            for (int x = 0; x + locPerV - 1 < in.dstSize; x += 2) {
                REP(i, locPerV) {
                    ret.setV(x + i, y + i, v, in);
                }
                //debugPrintMapper(ret);
                ++v;
                if (v == in.srcV) break;
            }
            if (v == in.srcV) break;

            int startX = 1;
            while (true) {
                if (startX + 1 >= locPerV) break;
                startX += 2;
            }
            for (int x = startX; x < in.dstSize; x += 2) {
                REP(i, locPerV) {
                    ret.setV(x - i, y + i, v, in);
                }
                //debugPrintMapper(ret);
                ++v;
                if (v == in.srcV) break;
            }
            y += locPerV;
            if (v == in.srcV) break;
        }

        // 頂点が埋まらない場合、残りは他の方法で埋める
        if (v != in.srcV) {
            makeInitialMapperWithRandomLine(ret, v);
        }

        return ret;
    }

    // 規則正しい2x2の初期盤面を作成（検討したが途中で放棄）
    Mapper makeInitialMapper2x2() {
        Mapper ret;
        ret.init(in);

        int locPerV = in.dstV / in.srcV;

        if (locPerV == 1) return makeInitialMapper();

        // とりあえず2x2で並べる

        auto squareSize = getSrcSize(in.srcV / 2);
        auto offset = (in.dstSize - squareSize * 2) / 2;

        bool flip = true;
        int y = offset;
        int x = offset;
        int v = 0;
        while (true) {
            if (v == in.srcV) break;
            ret.setV(x, y, v, in);
            ret.setV(x + 1, y + 1, v, in);
            ++v;

            if (v == in.srcV) break;
            ret.setV(x + 1, y, v, in);
            ret.setV(x, y + 1, v, in);
            ++v;

            x += 2;

            if ((v / 2) % squareSize == 0) {
                x = offset;
                y += 2;
            }
        }
        //debugPrintMapper(ret);

        // 頂点が埋まらない場合、残りは他の方法で埋める
        if (v != in.srcV) {
            makeInitialMapperWithRandomLine(ret, v);
            return ret;
        }
        else {
            Mapper ret2(ret);

            // 周囲にある数値を延長する
            REP(x, in.dstSize) {
                // 上側
                REP(y, in.dstSize) {
                    auto val = ret.getV(x, y);
                    if (val != -1) {
                        // 右上に伸ばすか左上に伸ばすか決める
                        int dx = (x % 2) ? 1 : -1;

                        int y2 = y - 1;
                        int x2 = x + dx;
                        while (true) {
                            if (ret2.inRange(x2, y2) && ret2.getV(x2, y2) == -1) {
                                ret2.setV(x2, y2, val, in);
                                x2 += dx;
                                y2--;
                            }
                            else {
                                break;
                            }
                        }
                        break;
                    }
                }
                // 下側
                for (int y = in.dstSize - 1; y >= 0; --y) {
                    auto val = ret.getV(x, y);
                    if (val != -1) {
                        int dx = (x % 2) ? 1 : -1;
                        int y2 = y + 1;
                        int x2 = x + dx;
                        while (true) {
                            if (ret2.inRange(x2, y2) && ret2.getV(x2, y2) == -1) {
                                ret2.setV(x2, y2, val, in);
                                x2 += dx;
                                y2++;
                            }
                            else {
                                break;
                            }
                        }
                        break;
                    }
                }
            }
            REP(y, in.dstSize) {
                // 左側
                REP(x, in.dstSize) {
                    auto val = ret.getV(x, y);
                    if (val != -1) {
                        int dy = (y % 2) ? 1 : -1;
                        int x2 = x - 1;
                        int y2 = y + dy;
                        while (true) {
                            if (ret2.inRange(x2, y2) && ret2.getV(x2, y2) == -1) {
                                ret2.setV(x2, y2, val, in);
                                y2 += dy;
                                x2--;
                            }
                            else {
                                break;
                            }
                        }
                        break;
                    }
                }
                // 右側
                for (int x = in.dstSize - 1; x >= 0; --x) {
                    auto val = ret.getV(x, y);
                    if (val != -1) {
                        int dy = (y % 2) ? 1 : -1;
                        int x2 = x + 1;
                        int y2 = y + dy;
                        while (true) {
                            if (ret2.inRange(x2, y2) && ret2.getV(x2, y2) == -1) {
                                ret2.setV(x2, y2, val, in);
                                y2 += dy;
                                x2++;
                            }
                            else {
                                break;
                            }
                        }
                        break;
                    }
                }
            }

            return ret2;
        }

    }

    short decideSrcV1(
        const short srcU, const vector<vector<short>>& dstEdgesVec,
        const vector<short>& curSrc2dst, const vector<short>& curDst2src)
    {
        // srcUが隣接している点を一つ選び、srcXとする。その対応点はdstX。
        auto neiSize = SIZE(in.srcEdgesVec[srcU]);
        auto srcX = in.srcEdgesVec[srcU][rand() % neiSize];
        auto dstX = curSrc2dst[srcX];

        // dstXの隣接点を一つ選び、dstYとする。その対応点をsrcVとする。
        auto neiSize2 = SIZE(dstEdgesVec[dstX]);
        auto dstY = dstEdgesVec[dstX][rand() % neiSize2];

        return curDst2src[dstY];
    }

    short decideSrcV2(
        const short srcU, const vector<vector<short>>& dstEdgesVec,
        const vector<short>& curSrc2dst, const vector<short>& curDst2src)
    {
        vector<int> dstYcount(in.srcV);

        // srcUが隣接している点srcIそれぞれについて、対応点dstIを求め、
        // それに隣接する点に投票
        for (auto srcI : in.srcEdgesVec[srcU]) {
            auto dstI = curSrc2dst[srcI];
            for (auto dstJ : dstEdgesVec[dstI]) {
                ++dstYcount[dstJ];
            }
        }

        // もっとも投票されたものからランダムで一つ選ぶ
        auto mx = *max_element(ALL(dstYcount));
        vector<short> cands;
        REP(i, in.srcV) {
            if (dstYcount[i] == mx) {
                cands.push_back(i);
            }
        }
        auto candY = cands[myrand() % SIZE(cands)];
        return curDst2src[candY];
    }

    int calcDiffScore(const int srcU, const int srcV,
        const int dstU, const int dstV,
        const vector<vector<short>>& dstEdgesVec,
        vector<short>& curSrc2dst, vector<short>& curDst2src)
    {
        int diffScore = 0;
        for (auto dstNei : dstEdgesVec[dstU]) {
            if (dstNei == dstV) continue;
            auto srcNei = curDst2src[dstNei];
            diffScore -= in.hasSrcEdge(srcU, srcNei);
            diffScore += in.hasSrcEdge(srcV, srcNei);
        }
        for (auto dstNei : dstEdgesVec[dstV]) {
            if (dstNei == dstU) continue;
            auto srcNei = curDst2src[dstNei];
            diffScore -= in.hasSrcEdge(srcV, srcNei);
            diffScore += in.hasSrcEdge(srcU, srcNei);
        }
        return diffScore;
    }

    void randomSwapSub2(
        const vector<vector<short>>& dstEdgesVec,
        vector<short>& curSrc2dst, vector<short>& curDst2src, int& curScore,
        const Mapper& bestMapper, // for debug
        const ll allowedTime, const ll ellapsedTime,
        const int tryNum
    ) {

        short srcU = myrand() % in.srcV;
        short srcV = -1;

        if (tryNum % 10 == 9) {
            // 最もスコアが上がりそうな点と入れ替える
            srcV = decideSrcV2(srcU, dstEdgesVec, curSrc2dst, curDst2src);
        }
        else {
            // 隣接関係がある点と入れ替える
            srcV = decideSrcV1(srcU, dstEdgesVec, curSrc2dst, curDst2src);
        }

        if (srcU == srcV) return;

        // uとvを入れ替えたときのスコアの増減を調べる
        auto dstU = curSrc2dst[srcU];
        auto dstV = curSrc2dst[srcV];
        auto diffScore = calcDiffScore(
            srcU, srcV, dstU, dstV,
            dstEdgesVec, curSrc2dst, curDst2src
        );

        // 遷移確率
        double timeRate = (double)ellapsedTime / allowedTime;
        double threshold = 0.0; // 1.0なら確実に遷移する  0.0なら確実に遷移しない
        double threshold2 = 0.001;
        if (timeRate > 0.98) {
            threshold = 0.0;
            threshold2 = 0.0;
        }
        else {
            threshold = (1.0 - timeRate * 2.0);  // 最初1.0, 最後0.0
            threshold = max(threshold, 0.01);
        }
        double prob = (double)rand() / RAND_MAX;

        // 遷移確率 50% -> 0%とする

        //const double T = 0.55;
        //double th = exp(diffScore / T);

        // 遷移する場合
        //if ((1 - th) < prob) {
        if (diffScore >= 0 || (diffScore > -2 && prob < threshold) || (diffScore > -4 && prob < threshold2)) {
            //if (diffScore > 0) {
            //fprintf(stderr, "%d(%d, %d) <-> %d(%d, %d)\n", v1, x1, y1, v2, x2, y2);
            curScore += diffScore * 100;
            //debugPrintMapper(curMap);

            curSrc2dst[srcU] = dstV;
            curSrc2dst[srcV] = dstU;
            curDst2src[dstU] = srcV;
            curDst2src[dstV] = srcU;
        }

        //cerr << diffScore << " / " << curScore << " / " << threshold << endl;

        return;
    }

    Mapper makeMapperFromSrc2dst(const vector<short>& bestSrc2dst, const Mapper& bestMapper) {
        vector<short> bestDst2src(in.srcV);

        // まず逆引きを作成
        REP(u, in.srcV) {
            auto v = bestSrc2dst[u];
            bestDst2src[v] = u;
        }

        // 次に新しいMapperを作成
        Mapper newBest;
        newBest.init(in);

        REP(y, in.dstSize) {
            REP(x, in.dstSize) {
                auto oldV = bestMapper.getV(x, y);
                if (oldV != -1) {
                    auto newV = bestDst2src[oldV];
                    newBest.setV(x, y, newV, in);
                }
            }
        }

        return newBest;
    }

    void tryAllSwap(vector<vector<short>>& dstEdgesVec, vector<short>& bestSrc2dst, vector<short>& bestDst2src, int& bestScore) {
        REP(srcU, in.srcV - 1) {
            FOR(srcV, srcU + 1, in.srcV) {
                // uとvを入れ替えたときのスコアの増減を調べる
                auto dstU = bestSrc2dst[srcU];
                auto dstV = bestSrc2dst[srcV];
                auto diffScore = calcDiffScore(
                    srcU, srcV, dstU, dstV,
                    dstEdgesVec, bestSrc2dst, bestDst2src
                );

                if (diffScore > 0) {
                    cerr << "score up! " << (diffScore * 100) << endl;
                }
            }
        }
    }

    // 頂点をランダムに２個選んで、まるごと入れ替える
    void randomSwap(Mapper& bestMapper, int& bestScore, ll allowedTime) {

        auto curMapper = bestMapper;
        auto curScore = bestScore;
        Timer timer;
        timer.start();

        // 隣接関係を抽出
        vector<vector<short>> dstEdgesVec(in.srcV);
        REP(u, in.srcV - 1) {
            FOR(v, u + 1, in.srcV) {
                if (bestMapper.adjacents[u][v] > 0) {
                    dstEdgesVec[u].push_back(v);
                    dstEdgesVec[v].push_back(u);
                }
            }
        }

        // このマッピングを今後変えていく
        vector<short> curSrc2dst(in.srcV);
        vector<short> curDst2src(in.srcV);
        REP(u, in.srcV) {
            curSrc2dst[u] = u;
            curDst2src[u] = u;
        }

        auto bestSrc2dst = curSrc2dst;
        curScore = bestScore;

        // 2頂点の入れ替えを試す
        int tryNum = 0;
        ll ellapsedTime = 0;
        while (true) {

            if (tryNum % 100 == 0) {
                ellapsedTime = timer.milli();
            }

            // 2点をランダムに入れ替え
            randomSwapSub2(
                dstEdgesVec, curSrc2dst, curDst2src, curScore,
                bestMapper,
                allowedTime,
                ellapsedTime,
                tryNum
            );

            if (curScore > bestScore) {
                bestScore = curScore;
                bestSrc2dst = curSrc2dst;
            }

            if (ellapsedTime > MAX_TIME1) {
                break;
            }

            ++tryNum;
        }
        cerr << "tryNum randomSwap: " << tryNum << endl;

        // 逆引きを作成
        vector<short> bestDst2src(in.srcV);
        REP(u, in.srcV) {
            auto v = bestSrc2dst[u];
            bestDst2src[v] = u;
        }

        // さらに全点間のswapを試す -> 効果なし
        //tryAllSwap(dstEdgesVec, bestSrc2dst, bestDst2src, bestScore);

        // マッピング結果をもとに bestMapper を更新
        bestMapper = makeMapperFromSrc2dst(bestSrc2dst, bestMapper);
        bestScore = calcScore(bestMapper); // 精密に求める
    }

    // 頂点をランダムに１個選ぶ。その値を変えても連結性が保たれる場合、
    // 候補を全通り試し、もっともよいものを選ぶ。
    void randomMove(Mapper& curMap, int& curScore, ll ellapsedTime)
    {
        // 頂点をランダムに1個選ぶ
        auto x = myrand() % in.dstSize;
        auto y = myrand() % in.dstSize;

        auto cur = curMap.getV(x, y);

        // すでに数字がある場合、その数字を消して連続性が保たれない場合、終了
        if (cur != -1) {
            if (!curMap.canDelete(x, y))
            {
                return;
            }
        }

        // 周囲にある番号をランダムに一つ選択して試す
        int d = rand() % 8;
        auto n = -1;
        REP(d2, 8) {
            auto x2 = x + dx8[(d + d2) % 8];
            auto y2 = y + dy8[(d + d2) % 8];
            n = curMap.getV(x2, y2);
            if (n != -1 || n != cur) break;
        }

        // 変化なければ終了
        if (n == cur) return;

        // 試す
        auto edgeDiff = curMap.setV(x, y, n, in);

        // 点数が上がるなら採用
        if (cur == -1 || edgeDiff > 0) {
            curScore += edgeDiff * 100; // 近似にしかなってないので注意
            return;
        }
        // 元に戻す
        else {
            curMap.setV(x, y, cur, in);
        }
    }

    void solve()
    {
        // 初期解を生成
        auto bestMapper1 = makeInitialMapperNxN();
        auto bestScore1 = calcScore(bestMapper1);

        auto bestMapper2 = makeInitialMapperDiagonal();
        auto bestScore2 = calcScore(bestMapper2);

        // いい方を選ぶ
        Mapper bestMapper;
        int bestScore;
        if (bestMapper1.getPotential() > bestMapper2.getPotential()) {
            bestScore = bestScore1;
            bestMapper = bestMapper1;
        }
        else {
            bestScore = bestScore2;
            bestMapper = bestMapper2;
        }
        cerr << "initial map" << endl;
        cerr << "initial score:" << bestScore << endl;

        debugPrintMapper(bestMapper);

        // potentialの増加を狙う
        REP(rep, 20) {
            int curPot = bestMapper.getPotential();
            REP(y, in.dstSize) {
                REP(x, in.dstSize) {
                    if (bestMapper.canDelete(x, y)) {
                        auto oldV = bestMapper.getV(x, y);
                        REP(d, 8) {
                            int x2 = x + dx8[d];
                            int y2 = y + dy8[d];
                            auto newV = bestMapper.getV(x2, y2);
                            if (newV == -1) continue;
                            bestMapper.setV(x, y, newV, in);
                            int newPot = bestMapper.getPotential();
                            if (newPot >= curPot) {
                                newPot = curPot;
                            }
                            else {
                                bestMapper.setV(x, y, oldV, in);
                            }
                        }
                    }
                }
            }
        }

        debugPrintMapper(bestMapper);

        // 2頂点の入れ替えで焼きなまし
        randomSwap(bestMapper, bestScore, MAX_TIME1);

        auto curMapper = bestMapper;
        auto curScore = bestScore = calcScore(bestMapper);
        cerr << "bestScore second:" << bestScore << endl;
        debugPrintMapper(bestMapper);

        int tryNum = 0;
        ll ellapsedTime = 0;
        while (true) {
            // 経過時間
            if (tryNum % 100 == 0) {
                ellapsedTime = getEllapsedTime();
            }

            // 点数が上がるようにランダムに頂点を変化
            randomMove(curMapper, curScore, ellapsedTime);

            if (curScore > bestScore) {
                // 正確な値を計算
                curScore = calcScore(curMapper);

                // その上で改めてベストかどうか判定
                if (curScore > bestScore) {
                    bestScore = curScore;
                    bestMapper = curMapper;
                }
            }

            if (ellapsedTime > MAX_TIME2) {
                break;
            }

            ++tryNum;
        }

        cerr << "tryNum: " << tryNum << endl;
        cerr << "score: " << bestScore << endl;
        debugPrintMapper(bestMapper);
        ans = bestMapper;
        return;
    }

    int calcScore(Mapper& ans)
    {
        // もし割り当てのない点があれば0点
        REP(v, in.srcV) {
            if (!ans.count[v]) return 0;
        }

        // TODO: 連結判定はしていない

        m_prevEdgeNum = 0;
        m_prevAdd = 0;
        REP(u, in.srcV - 1) {
            FOR(v, u + 1, in.srcV) {
                if (ans.adjacents[u][v] && in.hasSrcEdge(u, v)) {
                    m_prevAdd++;
                    m_prevEdgeNum++;
                }
            }
        }
        int score = 5000 + m_prevAdd * 100;

        // bonus
        if (m_prevAdd == in.srcE) {
            score += 100000;
            m_prevBonus = 100000;
        }
        else {
            m_prevBonus = 0;
        }

        // penalty
        m_prevLoss = 0;
        REP(v, in.srcV) {
            m_prevLoss += ans.count[v] - 1;
        }
        score -= m_prevLoss;

        //if (score != calcScoreReference(ans)) {
        //    cerr << "error!!" << endl;
        //    cerr << "reference: " << calcScoreReference(ans) << endl;
        //}
        return score;
    }

    int calcScoreReference(Mapper& ans)
    {
        int score = 5000;
        set<pair<int, int>> seen;
        vector<int> setSize(in.srcV);
        REP(y, in.dstSize) {
            REP(x, in.dstSize) {
                auto cur = ans.getV(x, y);
                if (cur == -1) continue;
                int dx[] = { 1, 1, 0, -1 };
                int dy[] = { 0, 1, 1, 1 };
                REP(d, 4) {
                    auto y2 = y + dy[d];
                    auto x2 = x + dx[d];
                    auto nei = ans.getV(x2, y2);
                    if (nei == -1) continue;
                    auto mn = min(cur, nei);
                    auto mx = max(cur, nei);
                    if (cur != nei && in.hasSrcEdge(mn, mx) && !seen.count(mp(mn, mx))) {
                        score += 100;
                        seen.insert(mp(mn, mx));
                    }
                }
                ++setSize[cur];
            }
        }
        // bonus
        if (SIZE(seen) == in.srcE) score += 100000;
        // penalty
        REP(v, in.srcV) {
            score -= (setSize[v] - 1);
        }
        return score;
    }
    void printAnswer()
    {
        vector<vector<int>> tmp(in.srcV);
        REP(y, in.dstSize) {
            REP(x, in.dstSize) {
                auto dst = y * in.dstSize + x;
                auto src = ans.getV(x, y);
                if (src != -1) {
                    tmp[src].pb(dst);
                }
            }
        }
        REP(i, in.srcV) {
            cout << SIZE(tmp[i]);
            for (auto e : tmp[i]) {
                cout << " " << (e + 1);
            }
            cout << endl;
        }
    }
};

int main(void)
{
    cin.sync_with_stdio(false);

    Solver sol;
    sol.start();
    sol.readInput();
    sol.solve();
    sol.printAnswer();

    return 0;
}