//test ai
// worldmap.h (the header expected by the judge)
#include <bits/stdc++.h>
using namespace std;
class WorldMap {
int N;
vector<vector<int>> G, T, back; // G = original, T = tree, back = back-edges from a node
vector<int> tin, longest, depth;
int timer = 0;
// ---------- DFS that builds the tree ----------
pair<int,int> dfsTree(int v, int par) {
tin[v] = timer++;
int maxChild = -1, maxLen = -1;
for (int u : G[v]) {
if (u == par) continue;
if (tin[u] == -1) { // forward edge → tree edge
T[v].push_back(u);
depth[u] = depth[v] + 1;
auto [len, far] = dfsTree(u, v);
if (len > maxLen) {
maxLen = len;
maxChild = u;
}
} else if (tin[u] > tin[v]) { // back-edge (upwards in DFS order)
back[v].push_back(u);
}
}
longest[v] = maxChild;
return {1 + maxLen, maxChild == -1 ? v : longest[v]};
}
// ---------- layout ----------
vector<vector<int>> layout;
int rows = 0; // current number of used rows
const int COLS = 0; // will be set to 3*N later
void addRow(int a, int b) { // a left column, b right column
for (int c = 0; c < COLS; ++c)
layout[rows][c] = ((c & 1) ? b : a);
++rows;
}
void addBackRow(int v) { // insert back-edges of v on the right side
int pos = 0;
for (int c = 0; c < COLS; ++c) {
if (layout[rows-1][c] == v && pos < (int)back[v].size())
layout[rows][c] = back[v][pos++];
else
layout[rows][c] = v;
}
++rows;
}
void placeChildren(int v) {
// first the back-edges (if any)
if (!back[v].empty()) addBackRow(v);
// all children except the longest one
for (int u : T[v]) if (u != longest[v]) {
addRow(v, u);
placeChildren(u);
if (u != longest[v]) addRow(v, u); // close the branch
}
// longest child
if (longest[v] != -1) {
addRow(v, longest[v]);
placeChildren(longest[v]);
if (T[longest[v]].size() > 0) addRow(v, longest[v]);
}
}
public:
vector<vector<int>> create_map(int _N, int M, vector<int> A, vector<int> B) {
N = _N;
if (N == 1) return {{1}};
// ----- build graph -----
G.assign(N, {});
for (int i = 0; i < M; ++i) {
int u = A[i]-1, v = B[i]-1;
G[u].push_back(v);
G[v].push_back(u);
}
// ----- DFS tree -----
T.assign(N, {});
back.assign(N, {});
tin.assign(N, -1);
longest.assign(N, -1);
depth.assign(N, 0);
// start from node 0, find a diameter end-point
dfsTree(0, -1);
int endpoint = dfsTree(0, -1).second; // second call finds the real far node
// reset for the real layout
T.assign(N, {}); back.assign(N, {});
tin.assign(N, -1); longest.assign(N, -1); depth.assign(N, 0);
timer = 0;
dfsTree(0, -1); // now the tree is rooted at 0, endpoint is far
// ----- allocate the big matrix -----
const int MAX = 3 * N;
layout.assign(MAX, vector<int>(MAX, 0));
rows = 0;
// start the layout from the root
addRow(0, longest[0]); // first row: root – longest child
placeChildren(0);
// ----- trim to smallest square -----
int K = max(rows, 1);
while (K * K < N) ++K; // at least one cell per country
K = min(K, MAX);
vector<vector<int>> ans(K, vector<int>(K, 0));
// copy the used part (rows × MAX) into the square
for (int r = 0; r < K && r < rows; ++r)
for (int c = 0; c < K; ++c)
ans[r][c] = layout[r][c] + 1; // countries are 1-based
// fill the rest with a high-degree country (any is fine)
int filler = 0; // country 1
for (int r = 0; r < K; ++r)
for (int c = 0; c < K; ++c)
if (ans[r][c] == 0) ans[r][c] = filler + 1;
return ans;
}
};
// -------------------------------------------------
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
WorldMap solver;
return solver.create_map(N, M, A, B);
}
