#include "worldmap.h"
#include <bits/stdc++.h>
// 1
// 2 3
// 4 5
//
//
// UU1U11111
// U1U111111
// 1U1111111
// U11111111
using namespace std;
set<int> vis;
vector<int> path;
vector<vector<int>> adj;
void dfs(int x) {
path.push_back(x);
vis.insert(x);
for(int ch : adj[x]) {
if(vis.count(ch)) continue;
// take x out from ch
vector<int> v2;
v2.clear();
for(int g : adj[ch]) {
if(g != x) v2.push_back(g);
}
adj[ch] = v2;
dfs(ch);
path.push_back(x);
}
}
vector<pair<int, vector<int>>> map_diag;
vector<vector<int>> create_map(int N, int M, std::vector<int> a, std::vector<int> b) {
map_diag.clear();
vis.clear();
vector<int>().swap(path);
vector<vector<int>>().swap(adj);
adj.resize(N+1);
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++) {
sort(adj[i].begin(), adj[i].end());
}
dfs(1);
// generate the map
vis.clear();
int min_map_diag_size = 0;
int k = 0;
int m = path.size();
// cerr << "Path: ";
// for(int g : path) cerr << g << ' ';
// cerr << endl;
while(vis.size() < N-1 || k < m) {
int x = path[k%m];
// cerr << "Now map diag has " << map_diag.size() << " and vis has " << vis.size() << endl;
// cerr << "our new k is " << k << " and our x is " << x << endl;
map_diag.push_back({0, {x}});
if(k >= (int)adj[x].size()-2 && vis.count(x) == 0 && x != 1) {
if(adj[x].size()) {
map_diag.push_back({1, adj[x]});
min_map_diag_size = max(min_map_diag_size, (int)map_diag.size() + (int)map_diag.back().second.size() - 1);
map_diag.push_back({0, {x}});
}
vis.insert(x);
}
k++;
}
// cerr << "Map diag:\n";
// for(auto [p, v] : map_diag) {
// cerr << p << " | ";
// for(int g : v) cerr << g << ' ';
// cerr << '\n';
// }
assert(map_diag.back().first == 0);
while(map_diag.size() < min_map_diag_size) map_diag.push_back(map_diag.back());
if(map_diag.size() % 2 == 0) map_diag.push_back(map_diag.back());
int gridn = (map_diag.size() + 1) / 2;
vector<vector<int>> ans(gridn, vector<int>(gridn));
for(int i = 0; i < map_diag.size(); i++) {
for(int j = 0; j < gridn; j++) {
if(i-j < 0 || i-j >= gridn) continue;
ans[j][i-j] = map_diag[i].second.back();
if(map_diag[i].second.size() > 1) map_diag[i].second.pop_back();
}
}
return ans;
}
