docker_space/frontier_cs_6/logs/gen_2.cpp

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

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;
    vector<int> order;
    vector<pair<int,int>> pos;
};

static int pack_children_height(const vector<int>& order, const vector<Layout>& lay, int innerW) {
    if (order.empty()) return 0;
    int x = 0, y = 0, rowH = 0;
    for (int v : order) {
        int wv = lay[v].w;
        int hv = lay[v].h;
        if (x > 0 && x + wv > innerW) {
            y += rowH + 1;
            x = 0;
            rowH = 0;
        }
        x += wv;
        if (x < innerW) x += 1;
        rowH = max(rowH, hv);
    }
    return y + rowH;
}

static int pack_children_positions(const vector<int>& order, const vector<Layout>& lay, int innerW, vector<pair<int,int>>& outPos) {
    outPos.clear();
    if (order.empty()) return 0;
    outPos.reserve(order.size());
    int x = 0, y = 0, rowH = 0;
    for (int v : order) {
        int wv = lay[v].w;
        int hv = lay[v].h;
        if (x > 0 && x + wv > innerW) {
            y += rowH + 1;
            x = 0;
            rowH = 0;
        }
        outPos.push_back({y, x});
        x += wv;
        if (x < innerW) x += 1;
        rowH = max(rowH, hv);
    }
    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 slotRows = 2;
    int gadgetHConst = 3;

    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) {
            // BFS
            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 {
            // DFS
            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);
                    }
                }
            }
        }
        // Handle disconnected: connect isolated nodes to root
        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;
            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_dims(int u, int& gW, int& gH) {
        int g = (int)gadgets[u].size();
        if (g == 0) { gW = 0; gH = 0; return; }
        // Try different arrangements and pick most compact
        int bestGW = INT_MAX, bestGH = INT_MAX;
        long long bestArea = (long long)INT_MAX * INT_MAX;
        for (int rows = 1; rows <= g; rows++) {
            int cols = (g + rows - 1) / rows;
            int gw = 2 * cols - 1;
            int gh = 2 * rows - 1;
            long long area = (long long)gw * gh;
            int maxDim = max(gw, gh);
            int bestMaxDim = max(bestGW, bestGH);
            if (maxDim < bestMaxDim || (maxDim == bestMaxDim && area < bestArea)) {
                bestGW = gw;
                bestGH = gh;
                bestArea = area;
            }
        }
        gW = bestGW;
        gH = bestGH;
    }

    int gadgetRows(int u) {
        int g = (int)gadgets[u].size();
        if (g == 0) return 0;
        int gW, gH;
        compute_gadget_dims(u, gW, gH);
        return (gH + 1) / 2;
    }

    int gadgetCols(int u) {
        int g = (int)gadgets[u].size();
        if (g == 0) return 0;
        int gW, gH;
        compute_gadget_dims(u, gW, gH);
        return (gW + 1) / 2;
    }

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

        Layout L;
        int gW, gH;
        compute_gadget_dims(u, gW, gH);
        L.gadgetW = gW;
        L.gadgetH = gH;

        L.order = children[u];
        sort(L.order.begin(), L.order.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;
        });

        int maxChildW = 0;
        for (int v : L.order) maxChildW = max(maxChildW, lay[v].w);

        int minInnerW = max(1, max(maxChildW, gW));
        int bestInnerW = -1;
        int bestInnerH = -1;
        int bestChildrenH = -1;
        int bestSep = 0;
        long long bestMetric = (1LL << 60);

        for (int innerW = minInnerW; innerW <= Kmax - 2; innerW++) {
            int cH = pack_children_height(L.order, lay, innerW);
            int sep = (cH > 0 && gH > 0) ? 1 : 0;
            int innerH = cH + sep + gH;
            if (innerH < 1) innerH = 1;

            int W = innerW + 2;
            int H = innerH + 2;
            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;
            }
        }
        if (bestInnerW == -1) return false;

        L.innerW = bestInnerW;
        L.innerH = bestInnerH;
        L.w = bestInnerW + 2;
        L.h = bestInnerH + 2;
        L.childrenH = bestChildrenH;
        L.sep = bestSep;
        L.gadgetStartY = 1 + bestChildrenH + bestSep;

        pack_children_positions(L.order, lay, bestInnerW, L.pos);

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

    void paint(int u, int top, int left, vector<vector<int>>& C) {
        const Layout& L = lay[u];
        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 + 1 + y, left + 1 + x, C);
        }

        int g = (int)gadgets[u].size();
        if (g > 0) {
            int baseY = top + L.gadgetStartY;
            int baseX = left + 1;
            int gW, gH;
            compute_gadget_dims(u, gW, gH);
            int gCols = (gW + 1) / 2;
            for (int idx = 0; idx < g; idx++) {
                int rr = (idx / gCols) * 2;
                int cc = (idx % gCols) * 2;
                C[baseY + rr][baseX + cc] = gadgets[u][idx];
            }
        }
    }

    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)) continue;
            int rw = lay[r].w, rh = lay[r].h;
            if (rw <= K && rh <= K) {
                return max(rw, rh);
            }
        }
        return 241; // failed
    }

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

        // Try all roots with both BFS and DFS, pick best
        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;
                }
            }
        }

        // Rebuild with best root and mode
        build_spanning_tree_from(bestRoot, bestMode);
        assign_gadgets();
        lay.assign(N + 1, Layout());
        dfs_size(bestRoot, bestK);

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

        vector<vector<int>> C(Kfinal, vector<int>(Kfinal, bestRoot));
        paint(bestRoot, 0, 0, C);
        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;
}