#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
vector <vector <pair <int, bool>>> order;
vector <vector <int>> adj;
vector <bool> vis;
void dfs(int u, int p, int r) {
// cout << u << ' ';
if (adj[u].size() == 0) return;
order[r].push_back({u, 1});
order[r].push_back({u, 1});
order[r].push_back({u, 1});
for (auto v : adj[u]) {
if (vis[v]) continue;
vis[v] = true;
dfs(v, u, r);
order[r].push_back({u, 0});
}
if (p == -1) return;
}
vector<vector<int>> create_map(int n, int m, vector<int> a, vector<int> b) {
int k = 4 * n;
vis.assign(n + 1,0);
order.assign(n + 1, {});
vector<vector<int>> ans(k, vector<int>(k, 0));
adj.assign(n + 1, {});
int cnt[n + 1] = {0};
for (int i = 0;i < m;i++) {
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
}
for (int i = 1;i <= n;i++) {
vis.assign(n + 1, 0);
vis[i] = true;
dfs(i, -1, i);
}
int min = INT_MAX;
int root = 0;
for (int i = 1;i <= n;i++) {
if (order[i].size() < min) {
min = order[i].size();
root = i;
}
}
int i = 0;
for (;i < order[root].size();i++) {
if (i >= order[root].size()) break;
int x = order[root][i].first;
int y = order[root][i].second;
if (y == 0) {
for (int j = 0;j < k;j++) {
ans[i][j] = x;
}
}
else {
i += 2;
if (i >= order[root].size()) break;
for (int j = 0;j < k;j++) {
ans[i - 2][j] = x;
}
for (int j = 0;j < k;j++) {
ans[i][j] = x;
}
int iter = 0;
for (auto v : adj[x]) {
ans[i - 1][iter] = v;
ans[i - 1][iter + 1] = x;
iter += 2;
}
for (;iter < k;iter++) {
ans[i - 1][iter] = x;
}
}
}
for (;i < k;i++) {
for (int j = 0;j < k;j++) {
ans[i][j] = root;
}
}
return ans;
}
/*
1
4 4
1 2
1 3
2 4
3 4
1 2 4 3
*/
