#include <bits/stdc++.h>
#include "worldmap.h"
using namespace std;
vector<bool> vis;
vector<int> par, k;
vector<set<int>> t;
vector<vector<int>> g;
void dfs(int u) {
vis[u] = 1;
k.push_back(u);
for (auto v : g[u]) {
if (!vis[v]) {
par[v] = u;
dfs(v);
}
}
}
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;
}
};
vector<vector<int>> create_map(int n, int m, vector<int> a, vector<int> b) {
k.clear();
g.assign(n + 1, {});
t.assign(n + 1, {});
vis.assign(n + 1, 0);
par.assign(n + 1, -1);
DSU d(n + 1);
for (int i = 0; i < m; i++) {
if (d.link(a[i], b[i])) {
g[a[i]].push_back(b[i]);
g[b[i]].push_back(a[i]);
} else {
t[a[i]].insert(b[i]);
t[b[i]].insert(a[i]);
}
}
dfs(1);
vector<int> res = {1};
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;
}
