#include "worldmap.h"
#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
using namespace std;
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
vector<vector<pair<int, int>>> g(N + 1);
for (int i = 0; i < M; ++i) {
g[A[i]].push_back({B[i], i});
g[B[i]].push_back({A[i], i});
}
vector<int> col(N + 1);
vector<int> handled(M);
vector<vector<int>> ans(2 * N , vector<int> (2 * N));
int ind = 0;
bool flip = 0;
auto inc = [&]() {
ind++;
if (ind == sz(ans)) {
ind = 1;
flip = 1;
}
};
auto put = [&](int u) {
if (!flip) {
for (int y = ind, x = 0; y >= 0 && x <= ind; --y, ++x) {
ans[y][x] = u;
}
} else {
for (int y = sz(ans) - 1, x = ind; y >= ind && x < sz(ans); --y, ++x) {
ans[y][x] = u;
}
}
inc();
};
function<void(int, int)> dfs = [&](int u, int p) {
col[u] = 1;
put(u);
// cerr << "u: " << u << "\n";
vector<int> to_insert;
for (auto [v, i] : g[u]) {
if (v == p) continue;
if (col[v]) {
if (handled[i]) continue; // this adjacency is already accounted for
to_insert.push_back(v);
handled[i] = 1;
continue;
} else {
dfs(v, u);
}
handled[i] = 1;
put(u);
}
// cerr << "sz of to_insert: " << sz(to_insert) << "\n";
// for (int x : to_insert) cerr << x << " ";
// cerr << "\n";
if (!to_insert.empty()) {
while (!flip && ind + 1 < sz(to_insert)) {
// cerr << "iterating...: " << ind + 1 << "\n";
put(u);
}
if (!flip) {
for (int y = ind, x = 0; y >= 0 && x <= ind; --y, ++x) {
int num = u;
if (!to_insert.empty()) {
num = to_insert.back();
to_insert.pop_back();
}
// cerr << "y, x: " << y << " " << x << "\n";
// cerr << "back: " << num << "\n";
ans[y][x] = num;
}
} else {
for (int y = sz(ans) - 1, x = ind; y >= ind && x < sz(ans); --y, ++x) {
int num = u;
if (!to_insert.empty()) {
num = to_insert.back();
to_insert.pop_back();
}
ans[y][x] = num;
}
}
inc();
put(u);
}
};
dfs(1, 0);
for (auto& v : ans) {
for (int& x : v) {
if (x == 0) x = 1;
}
}
// while (ind < sz(ans)) put(1);
// cerr << "order:\n";
// for (int x : order) {
// cerr << x << " ";
// }
// cerr << "\n";
// int L = sz(order);
// vector<vector<int>> ans(L, vector<int>(L));
//
// for (int i = 0; i < L; ++i) {
// fill(all(ans[i]), order[i]);
// }
return ans;
}
