docker_space/frontier_cs_6/examples/grok4fastreasoning_2.cpp

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

vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
  vector<set<int>> adj(N + 1);
  for (int i = 0; i < M; i++) {
    int a = A[i], b = B[i];
    adj[a].insert(b);
    adj[b].insert(a);
  }
  int root = 1;
  vector<vector<int>> tree(N + 1);
  vector<bool> visited(N + 1, false);
  vector<int> parent(N + 1, -1);
  queue<int> qq;
  qq.push(root);
  visited[root] = true;
  while (!qq.empty()) {
    int u = qq.front();
    qq.pop();
    for (int v : adj[u]) {
      if (!visited[v]) {
        visited[v] = true;
        parent[v] = u;
        tree[u].push_back(v);
        qq.push(v);
      }
    }
  }
  vector<int> sub_height(N + 1), sub_width(N + 1);
  function<void(int, int)> comp_size = [&](int u, int p) {
    int numc = tree[u].size();
    int maxch = 0;
    int sumcw = 0;
    int nsep = max(0, numc - 1);
    for (int v : tree[u]) {
      comp_size(v, u);
      maxch = max(maxch, sub_height[v]);
      sumcw += sub_width[v];
    }
    int hchild = (numc == 0 ? 0 : maxch);
    sub_height[u] = 3 + hchild;
    int wchild = (numc == 0 ? 0 : sumcw + nsep);
    int deg = adj[u].size();
    int wblock = (deg == 0 ? 1 : 3 * deg);
    sub_width[u] = max(wblock, wchild);
  };
  comp_size(root, -1);
  int toth = sub_height[root];
  int totw = sub_width[root];
  int K = max(toth, totw);
  vector<vector<int>> C(K, vector<int>(K, 0));
  function<void(int, int, int)> do_place = [&](int u, int r0, int c0) {
    int sw = sub_width[u];
    int deg = adj[u].size();
    int wb = (deg == 0 ? 1 : 3 * deg);
    for (int i = 0; i < 3; i++) {
      int rr = r0 + i;
      if (rr >= K) continue;
      for (int j = 0; j < sw; j++) {
        int cc = c0 + j;
        if (cc >= K) break;
        C[rr][cc] = u;
      }
    }
    vector<int> neigh(adj[u].begin(), adj[u].end());
    int d = neigh.size();
    int pstart = c0;
    for (int k = 0; k < d; k++) {
      int v = neigh[k];
      int pc = pstart + 3 * k + 1;
      if (pc < c0 + sw && pc < K) {
        int rr = r0 + 1;
        if (rr < K) C[rr][pc] = v;
      }
    }
    auto& children = tree[u];
    int numc = children.size();
    if (numc == 0) return;
    int r1 = r0 + 3;
    if (r1 >= K) return;
    int maxch = 0;
    for (int v : children) maxch = max(maxch, sub_height[v]);
    vector<int> ch_starts(numc);
    int this_c = c0;
    int wchild_actual = 0;
    for (int i = 0; i < numc; i++) {
      int v = children[i];
      ch_starts[i] = this_c;
      do_place(v, r1, this_c);
      this_c += sub_width[v];
      wchild_actual += sub_width[v];
      if (i < numc - 1) {
        int sep_c = this_c;
        for (int rr = r1; rr < r1 + maxch && rr < K; rr++) {
          if (sep_c < K) C[rr][sep_c] = u;
        }
        this_c++;
        wchild_actual++;
      }
    }
    for (int i = 0; i < numc; i++) {
      int v = children[i];
      int startc = ch_starts[i];
      int endc = startc + sub_width[v] - 1;
      int child_h = sub_height[v];
      int gap_start_r = r1 + child_h;
      for (int rr = gap_start_r; rr < r1 + maxch && rr < K; rr++) {
        for (int cc = startc; cc <= endc && cc < K; cc++) {
          C[rr][cc] = v;
        }
      }
    }
    int children_end_c = c0 + wchild_actual;
    for (int rr = r1; rr < r1 + maxch && rr < K; rr++) {
      for (int cc = children_end_c; cc < c0 + sw && cc < K; cc++) {
        C[rr][cc] = u;
      }
    }
  };
  do_place(root, 0, 0, C);
  if (toth < K) {
    for (int r = toth; r < K; r++) {
      for (int j = 0; j < K; j++) {
        C[r][j] = C[toth - 1][j];
      }
    }
  }
  if (totw < K) {
    for (int j = totw; j < K; j++) {
      for (int i = 0; i < K; i++) {
        C[i][j] = C[i][totw - 1];
      }
    }
  }
  return C;
}

int main() {
  int T;
  cin >> T;
  for (int t = 0; t < T; t++) {
    int N, M;
    cin >> N >> M;
    vector<int> AA(M), BB(M);
    for (int i = 0; i < M; i++) {
      cin >> AA[i] >> BB[i];
    }
    auto cmap = create_map(N, M, AA, BB);
    int KK = cmap.size();
    cout << KK << endl;
    for (int q = 0; q < KK; q++) {
      if (q > 0) cout << " ";
      cout << KK;
    }
    cout << endl;
    cout << endl;
    for (int i = 0; i < KK; i++) {
      for (int j = 0; j < KK; j++) {
        if (j > 0) cout << " ";
        cout << cmap[i][j];
      }
      cout << endl;
    }
  }
  return 0;
}