#include <bits/stdc++.h>
#include "worldmap.h"
using namespace std;
vector<bool> vis;
vector<int> par, k;
vector<set<int>> t, g;
vector<vector<int>> adj;
// g - spanning tree
// t - not included in spanning tree
// adj - all
struct DSU {
int n;
vector<int> p;
// DSU(int sz) {
// n = sz;
// p.resize(n, -1);
// }
int root(int x) {
if (p[x] == -1) {
return x;
}
return p[x] = root(p[x]);
}
bool link(int u, int v) {
u = root(u);
v = root(v);
if (u == v) {
return false;
}
p[u] = v;
return true;
}
};
DSU dsu;
vector<int> d, from;
void get_dist(int u, vector<bool> &vis) {
vis[u] = 1;
for (auto v : adj[u]) {
if (!vis[v]) {
d[v] = d[u] + 1;
from[v] = u;
get_dist(v, vis);
}
}
}
pair<int, int> longest_path(int n) {
d.assign(n + 1, 0);
from.assign(n + 1, -1);
vector<bool> vis(n + 1);
get_dist(1, vis);
int u = max_element(d.begin(), d.end()) - d.begin();
fill(d.begin(), d.end(), 0);
fill(vis.begin(), vis.end(), 0);
get_dist(u, vis);
int v = max_element(d.begin(), d.end()) - d.begin();
int x = v;
while (from[x] != u) {
dsu.link(x, from[x]);
g[x].insert(from[x]);
g[from[x]].insert(x);
x = from[x];
}
if (u != x) {
dsu.link(u, x);
g[u].insert(x);
g[x].insert(u);
}
return {u, v};
}
void dfs(int u) {
vis[u] = 1;
k.push_back(u);
for (auto v : g[u]) {
if (!vis[v]) {
par[v] = u;
dfs(v);
}
}
}
vector<vector<int>> create_map(int n, int m, vector<int> a, vector<int> b) {
if (n == 1) {
return {{1}};
}
k.clear();
g.assign(n + 1, {});
t.assign(n + 1, {});
adj.assign(n + 1, {});
vis.assign(n + 1, 0);
par.assign(n + 1, -1);
dsu.p.assign(n + 1, -1);
for (int i = 0; i < m; i++) {
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
}
auto [d1, d2] = longest_path(n);
for (int i = 0; i < m; i++) {
if (g[a[i]].count(b[i])) {
continue;
}
if (dsu.link(a[i], b[i])) {
g[a[i]].insert(b[i]);
g[b[i]].insert(a[i]);
} else {
t[a[i]].insert(b[i]);
t[b[i]].insert(a[i]);
}
}
dfs(d1);
vector<int> res = {d1};
for (int i = 1; i < n; i++) {
int u = res.back(), v = k[i];
if (par[v] != u) {
u = par[u];
res.push_back(u);
while (u != par[v]) {
u = par[u];
res.push_back(u);
}
}
res.push_back(v);
}
int N = 4 * n, idx = 0;
vector<vector<int>> ans(N, vector<int>(N));
for (int i = 0; i < N; i++) {
if (idx >= res.size()) {
fill(ans[i].begin(), ans[i].end(), res.back());
continue;
}
int u = res[idx++];
fill(ans[i].begin(), ans[i].end(), u);
if (t[u].empty()) {
continue;
}
fill(ans[i + 2].begin(), ans[i + 2].end(), u);
int j = 0;
vector<int> rem;
for (auto v : t[u]) {
if (j + 2 >= N) break;
ans[i + 1][j++] = u;
ans[i + 1][j++] = v;
rem.push_back(v);
}
for (auto x : rem) {
t[u].erase(x);
t[x].erase(u);
}
for (; j < N; j++) {
ans[i + 1][j] = u;
}
i += 2;
}
return ans;
}
