docker_space/frontier_cs_6/solution.cpp

#include <bits/stdc++.h>
using namespace std;

struct GadgetCell {
    int row, col; // position relative to gadget area top-left
    int color;    // which gadget endpoint
};

struct Layout {
    int w = 0, h = 0;
    int innerW = 0, innerH = 0;
    int childrenH = 0;
    int sep = 0;
    int gadgetW = 0, gadgetH = 0;
    int gadgetStartY = 0;
    int gadgetPlacement = 0; // 0=below, 1=right
    int gadgetX = 0, gadgetY = 0; // relative position of gadget block in inner area
    vector<int> order;
    vector<pair<int,int>> pos;
    vector<GadgetCell> gadgetCells;
};

// Pack children with adjacency-aware gaps
// Children that are adjacent in the original graph can be placed without gaps
static int pack_children_height_adj(const vector<int>& order, const vector<Layout>& lay, int innerW,
    bool isEdge[41][41], vector<pair<int,int>>* outPos = nullptr) {
    if (order.empty()) return 0;
    if (outPos) { outPos->clear(); outPos->reserve(order.size()); }

    int x = 0, y = 0, rowH = 0;
    int prevV = -1;
    for (int v : order) {
        int wv = lay[v].w;
        int hv = lay[v].h;

        // Determine gap: 0 if previous child is adjacent, 1 otherwise
        int gap = 1; // default gap
        if (prevV != -1 && isEdge[prevV][v]) {
            gap = 0; // adjacent children can touch
        }

        if (x > 0 && x + gap + wv > innerW) {
            y += rowH + 1; // 1-row gap between shelves (always needed since different shelves might not be adjacent)
            x = 0;
            rowH = 0;
            prevV = -1;
            gap = 0; // first on new row
        }

        if (x > 0) x += gap;

        if (outPos) outPos->push_back({y, x});
        x += wv;
        rowH = max(rowH, hv);
        prevV = v;
    }
    return y + rowH;
}

struct Builder {
    int N = 0, M = 0;
    vector<int> A, B;

    vector<vector<int>> adj;
    bool isEdge[41][41]{};
    bool isTree[41][41]{};

    vector<int> parent;
    vector<vector<int>> children;
    vector<vector<int>> gadgets;

    vector<Layout> lay;

    int root = 1;

    // mode: 0=BFS, 1=DFS
    bool build_spanning_tree_from(int r, int mode = 0) {
        root = r;
        parent.assign(N + 1, -1);
        children.assign(N + 1, {});
        memset(isTree, 0, sizeof(isTree));
        parent[r] = 0;
        if (mode == 0) {
            queue<int> q;
            q.push(r);
            while (!q.empty()) {
                int u = q.front(); q.pop();
                for (int v : adj[u]) {
                    if (parent[v] == -1) {
                        parent[v] = u;
                        q.push(v);
                    }
                }
            }
        } else {
            stack<int> st;
            st.push(r);
            while (!st.empty()) {
                int u = st.top(); st.pop();
                for (int v : adj[u]) {
                    if (parent[v] == -1) {
                        parent[v] = u;
                        st.push(v);
                    }
                }
            }
        }
        for (int i = 1; i <= N; i++) {
            if (parent[i] == -1) parent[i] = r;
        }
        for (int i = 1; i <= N; i++) {
            if (i == r) continue;
            int p = parent[i];
            isTree[min(i,p)][max(i,p)] = true;
            children[p].push_back(i);
        }
        return true;
    }

    void assign_gadgets() {
        gadgets.assign(N + 1, {});
        vector<int> load(N + 1, 0);
        for (int i = 0; i < M; i++) {
            int a = A[i], b = B[i];
            int x = min(a,b), y = max(a,b);
            if (isTree[x][y]) continue;
            // Also check if both are children of the same parent - if so, their borders touching
            // already creates the edge (if we place them without gap)
            // This is handled by placing adjacent siblings together
            int u;
            if (load[a] < load[b]) u = a;
            else if (load[b] < load[a]) u = b;
            else u = min(a,b);
            int v = (u == a ? b : a);
            gadgets[u].push_back(v);
            load[u]++;
        }
    }

    void compute_gadget_layout(int u, int& gW, int& gH, vector<GadgetCell>& cells) {
        int g = (int)gadgets[u].size();
        cells.clear();
        if (g == 0) { gW = 0; gH = 0; return; }

        // Try different arrangements
        struct Candidate {
            int w, h;
            vector<GadgetCell> cells;
        };
        vector<Candidate> candidates;

        // 1. Checkerboard layouts
        for (int nRows = 1; nRows <= g; nRows++) {
            int cols = (g + nRows - 1) / nRows;
            int gw = 2 * cols - 1;
            int gh = 2 * nRows - 1;
            Candidate c;
            c.w = gw; c.h = gh;
            for (int idx = 0; idx < g; idx++) {
                int rr = (idx / cols) * 2;
                int cc = (idx % cols) * 2;
                c.cells.push_back({rr, cc, gadgets[u][idx]});
            }
            candidates.push_back(c);
        }

        // 2. Single-row adjacency-aware layout
        {
            // Order gadgets to maximize consecutive adjacencies
            vector<int> gOrder;
            {
                vector<bool> used(g, false);
                // Start from gadget with fewest adj
                int bestStart = 0;
                int minAdj = g;
                for (int i = 0; i < g; i++) {
                    int ac = 0;
                    for (int j = 0; j < g; j++) {
                        if (i != j && isEdge[gadgets[u][i]][gadgets[u][j]]) ac++;
                    }
                    if (ac < minAdj) { minAdj = ac; bestStart = i; }
                }
                gOrder.push_back(bestStart);
                used[bestStart] = true;
                while ((int)gOrder.size() < g) {
                    int last = gOrder.back();
                    int bestNext = -1, bestDeg = g+1;
                    for (int i = 0; i < g; i++) {
                        if (!used[i] && isEdge[gadgets[u][last]][gadgets[u][i]]) {
                            int deg = 0;
                            for (int j = 0; j < g; j++) {
                                if (!used[j] && j != i && isEdge[gadgets[u][i]][gadgets[u][j]]) deg++;
                            }
                            if (bestNext == -1 || deg < bestDeg) { bestNext = i; bestDeg = deg; }
                        }
                    }
                    if (bestNext == -1) {
                        for (int i = 0; i < g; i++) {
                            if (!used[i]) { bestNext = i; break; }
                        }
                    }
                    gOrder.push_back(bestNext);
                    used[bestNext] = true;
                }
            }

            // Single row
            {
                Candidate c;
                c.h = 1;
                int x = 0;
                for (int i = 0; i < g; i++) {
                    c.cells.push_back({0, x, gadgets[u][gOrder[i]]});
                    if (i + 1 < g) {
                        if (isEdge[gadgets[u][gOrder[i]]][gadgets[u][gOrder[i+1]]]) x += 1;
                        else x += 2;
                    }
                }
                c.w = x + 1;
                candidates.push_back(c);
            }

            // Multi-row adjacency-aware
            for (int nRows = 2; nRows <= g; nRows++) {
                int rowSize = (g + nRows - 1) / nRows;
                Candidate c;
                c.h = 2 * nRows - 1;
                int maxW = 0;
                for (int r = 0; r < nRows; r++) {
                    int start = r * rowSize;
                    int end = min(start + rowSize, g);
                    int x = 0;
                    for (int i = start; i < end; i++) {
                        c.cells.push_back({2*r, x, gadgets[u][gOrder[i]]});
                        if (i + 1 < end) {
                            if (isEdge[gadgets[u][gOrder[i]]][gadgets[u][gOrder[i+1]]]) x += 1;
                            else x += 2;
                        }
                    }
                    maxW = max(maxW, x + 1);
                }
                c.w = maxW;
                candidates.push_back(c);
            }
        }

        // Pick best candidate
        int bestIdx = 0;
        long long bestMetric = (1LL << 60);
        for (int i = 0; i < (int)candidates.size(); i++) {
            auto& c = candidates[i];
            int maxDim = max(c.w, c.h);
            long long area = (long long)c.w * c.h;
            long long metric = (long long)maxDim * 1000000LL + area;
            if (metric < bestMetric) {
                bestMetric = metric;
                bestIdx = i;
            }
        }

        gW = candidates[bestIdx].w;
        gH = candidates[bestIdx].h;
        cells = candidates[bestIdx].cells;
    }

    // Try multiple child orderings to find the best packing
    vector<int> best_child_order(int u, const vector<int>& childrenList) {
        if (childrenList.size() <= 1) return childrenList;

        // Try: sort by width desc, height desc (original)
        vector<vector<int>> orders;

        // Order 1: width desc
        {
            vector<int> o = childrenList;
            sort(o.begin(), o.end(), [&](int a, int b) {
                if (lay[a].w != lay[b].w) return lay[a].w > lay[b].w;
                return lay[a].h > lay[b].h;
            });
            orders.push_back(o);
        }

        // Order 2: height desc
        {
            vector<int> o = childrenList;
            sort(o.begin(), o.end(), [&](int a, int b) {
                if (lay[a].h != lay[b].h) return lay[a].h > lay[b].h;
                return lay[a].w > lay[b].w;
            });
            orders.push_back(o);
        }

        // Order 3: area desc
        {
            vector<int> o = childrenList;
            sort(o.begin(), o.end(), [&](int a, int b) {
                return lay[a].w * lay[a].h > lay[b].w * lay[b].h;
            });
            orders.push_back(o);
        }

        // Order 4: Try to group adjacent children together (greedy)
        {
            vector<int> o;
            vector<bool> used(N + 1, false);
            // Start with largest child
            vector<int> sorted = childrenList;
            sort(sorted.begin(), sorted.end(), [&](int a, int b) {
                return lay[a].w * lay[a].h > lay[b].w * lay[b].h;
            });
            o.push_back(sorted[0]);
            used[sorted[0]] = true;
            while ((int)o.size() < (int)childrenList.size()) {
                int last = o.back();
                int bestNext = -1;
                // Prefer adjacent children
                for (int v : sorted) {
                    if (!used[v] && isEdge[last][v]) {
                        bestNext = v;
                        break;
                    }
                }
                if (bestNext == -1) {
                    for (int v : sorted) {
                        if (!used[v]) { bestNext = v; break; }
                    }
                }
                o.push_back(bestNext);
                used[bestNext] = true;
            }
            orders.push_back(o);
        }

        return orders[0]; // For now, return first; we'll evaluate in dfs_size
    }

    bool dfs_size(int u, int Kmax, bool isRoot = false) {
        for (int v : children[u]) {
            if (!dfs_size(v, Kmax)) return false;
        }

        // Leaf with no gadgets: minimal 1x1 representation
        // The parent's border will create the tree edge
        if (children[u].empty() && gadgets[u].empty() && !isRoot) {
            Layout L;
            L.w = 1;
            L.h = 1;
            L.innerW = 1;
            L.innerH = 1;
            L.gadgetW = 0;
            L.gadgetH = 0;
            lay[u] = std::move(L);
            return true;
        }

        // Root can use border=0 to save space, but only if root color will still appear
        // Root color appears in: gap cells between children, gadget area, separators
        // Safe if: >= 2 children (gaps exist) or gadgets exist
        bool canSkipBorder = isRoot && (children[u].size() >= 2 || !gadgets[u].empty());
        int border = canSkipBorder ? 0 : 1;

        Layout L;
        int gW, gH;
        vector<GadgetCell> gCells;
        compute_gadget_layout(u, gW, gH, gCells);
        L.gadgetW = gW;
        L.gadgetH = gH;
        L.gadgetCells = gCells;

        // Try multiple child orderings
        vector<vector<int>> orders;
        {
            vector<int> o = children[u];
            sort(o.begin(), o.end(), [&](int a, int b) {
                if (lay[a].w != lay[b].w) return lay[a].w > lay[b].w;
                return lay[a].h > lay[b].h;
            });
            orders.push_back(o);
        }
        {
            vector<int> o = children[u];
            sort(o.begin(), o.end(), [&](int a, int b) {
                if (lay[a].h != lay[b].h) return lay[a].h > lay[b].h;
                return lay[a].w > lay[b].w;
            });
            orders.push_back(o);
        }
        // Greedy adjacency grouping order
        if (children[u].size() > 1) {
            vector<int> o;
            vector<bool> used(N + 1, false);
            vector<int> sorted = children[u];
            sort(sorted.begin(), sorted.end(), [&](int a, int b) {
                return lay[a].w * lay[a].h > lay[b].w * lay[b].h;
            });
            o.push_back(sorted[0]);
            used[sorted[0]] = true;
            while ((int)o.size() < (int)children[u].size()) {
                int last = o.back();
                int bestNext = -1;
                for (int v : sorted) {
                    if (!used[v] && isEdge[last][v]) { bestNext = v; break; }
                }
                if (bestNext == -1) {
                    for (int v : sorted) {
                        if (!used[v]) { bestNext = v; break; }
                    }
                }
                o.push_back(bestNext);
                used[bestNext] = true;
            }
            orders.push_back(o);
        }

        int bestInnerW = -1;
        int bestInnerH = -1;
        int bestChildrenH = -1;
        int bestSep = 0;
        int bestGadgetPlacement = 0;
        long long bestMetric = (1LL << 60);
        vector<int> bestOrder;

        for (auto& order : orders) {
            int maxChildW = 0;
            for (int v : order) maxChildW = max(maxChildW, lay[v].w);

            // Try gadget below children
            {
                int minInnerW = max(1, max(maxChildW, gW));
                for (int innerW = minInnerW; innerW <= Kmax - 2*border; innerW++) {
                    int cH = pack_children_height_adj(order, lay, innerW, isEdge);
                    int sep = (cH > 0 && gH > 0) ? 1 : 0;
                    int innerH = cH + sep + gH;
                    if (innerH < 1) innerH = 1;

                    int W = innerW + 2*border;
                    int H = innerH + 2*border;
                    if (W > Kmax || H > Kmax) continue;

                    long long metric = (long long)max(W, H) * 1000000LL + (long long)(W + H);
                    if (metric < bestMetric) {
                        bestMetric = metric;
                        bestInnerW = innerW;
                        bestInnerH = innerH;
                        bestChildrenH = cH;
                        bestSep = sep;
                        bestGadgetPlacement = 0;
                        bestOrder = order;
                    }
                }
            }

            // Try gadget to the right of children
            if (gW > 0 && gH > 0) {
                for (int childW = max(1, maxChildW); childW <= Kmax - 2*border; childW++) {
                    int cH = pack_children_height_adj(order, lay, childW, isEdge);
                    int totalW = childW + 1 + gW; // 1-cell gap + gadget width
                    if (cH < 1 && gH < 1) continue;
                    int innerH = max(cH, gH);
                    if (innerH < 1) innerH = 1;

                    int W = totalW + 2*border;
                    int H = innerH + 2*border;
                    if (W > Kmax || H > Kmax) continue;

                    long long metric = (long long)max(W, H) * 1000000LL + (long long)(W + H);
                    if (metric < bestMetric) {
                        bestMetric = metric;
                        bestInnerW = totalW;
                        bestInnerH = innerH;
                        bestChildrenH = cH;
                        bestSep = 0;
                        bestGadgetPlacement = 1;
                        bestOrder = order;
                    }
                }
            }
        }

        if (bestInnerW == -1) return false;

        L.order = bestOrder;
        L.innerW = bestInnerW;
        L.innerH = bestInnerH;
        L.w = bestInnerW + 2*border;
        L.h = bestInnerH + 2*border;
        L.childrenH = bestChildrenH;
        L.sep = bestSep;
        L.gadgetPlacement = bestGadgetPlacement;

        if (bestGadgetPlacement == 0) {
            L.gadgetStartY = border + bestChildrenH + bestSep;
            L.gadgetX = 0;
            L.gadgetY = bestChildrenH + bestSep;
        } else {
            int childW = bestInnerW - 1 - gW;
            L.gadgetX = childW + 1;
            L.gadgetY = 0;
        }

        int packW = (bestGadgetPlacement == 1) ? (bestInnerW - 1 - gW) : bestInnerW;
        pack_children_height_adj(L.order, lay, packW, isEdge, &L.pos);

        lay[u] = std::move(L);
        return true;
    }

    void paint(int u, int top, int left, vector<vector<int>>& C, bool isRoot = false) {
        const Layout& L = lay[u];
        int border = isRoot ? 0 : 1;

        // For 1x1 leaf nodes, just paint the single cell
        if (L.w == 1 && L.h == 1) {
            C[top][left] = u;
            return;
        }

        for (int i = 0; i < L.h; i++) {
            for (int j = 0; j < L.w; j++) {
                C[top + i][left + j] = u;
            }
        }

        for (size_t i = 0; i < L.order.size(); i++) {
            int v = L.order[i];
            int y = L.pos[i].first;
            int x = L.pos[i].second;
            paint(v, top + border + y, left + border + x, C);
        }

        if (!L.gadgetCells.empty()) {
            int baseY = top + border + L.gadgetY;
            int baseX = left + border + L.gadgetX;
            for (auto& gc : L.gadgetCells) {
                C[baseY + gc.row][baseX + gc.col] = gc.color;
            }
        }
    }

    int try_build(int r, int mode) {
        build_spanning_tree_from(r, mode);
        assign_gadgets();

        int Kstart = max(3, N);
        lay.assign(N + 1, Layout());

        for (int K = Kstart; K <= 240; K++) {
            lay.assign(N + 1, Layout());
            if (!dfs_size(r, K, true)) continue;
            int rw = lay[r].w, rh = lay[r].h;
            if (rw <= K && rh <= K) {
                return max(rw, rh);
            }
        }
        return 241;
    }

    vector<vector<int>> create_map() {
        if (N == 1) return vector<vector<int>>(1, vector<int>(1, 1));

        adj.assign(N + 1, {});
        memset(isEdge, 0, sizeof(isEdge));

        for (int i = 0; i < M; i++) {
            int a = A[i], b = B[i];
            isEdge[a][b] = isEdge[b][a] = true;
            adj[a].push_back(b);
            adj[b].push_back(a);
        }

        int bestK = 241;
        int bestRoot = 1;
        int bestMode = 0;
        for (int mode = 0; mode <= 1; mode++) {
            for (int r = 1; r <= N; r++) {
                int K = try_build(r, mode);
                if (K < bestK) {
                    bestK = K;
                    bestRoot = r;
                    bestMode = mode;
                }
            }
        }

        build_spanning_tree_from(bestRoot, bestMode);
        assign_gadgets();
        lay.assign(N + 1, Layout());
        dfs_size(bestRoot, bestK, true);

        int Kfinal = bestK;
        if (Kfinal > 240) Kfinal = 240;

        vector<vector<int>> C(Kfinal, vector<int>(Kfinal, bestRoot));
        paint(bestRoot, 0, 0, C, true);
        return C;
    }
};

static vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
    Builder b;
    b.N = N;
    b.M = M;
    b.A = std::move(A);
    b.B = std::move(B);
    return b.create_map();
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    if (!(cin >> T)) return 0;
    for (int tc = 0; tc < T; tc++) {
        int N, M;
        cin >> N >> M;
        vector<int> A(M), B(M);
        for (int i = 0; i < M; i++) cin >> A[i] >> B[i];

        auto C = create_map(N, M, A, B);
        int K = (int)C.size();

        cout << K << "\n";
        for (int i = 0; i < K; i++) {
            if (i) cout << ' ';
            cout << K;
        }
        cout << "\n\n";
        for (int i = 0; i < K; i++) {
            for (int j = 0; j < K; j++) {
                if (j) cout << ' ';
                cout << C[i][j];
            }
            cout << "\n";
        }
    }
    return 0;
}