#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define sp <<" "<<
#define endl "\n"
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
vector<vector<pair<int, int>>> adj(N+1);
for (int i = 0; i < M; i++) {
adj[A[i]].emplace_back(B[i], i);
adj[B[i]].emplace_back(A[i], i);
}
vector<int> sigma;
vector<bool> vis(N+1);
auto dfs = [&](auto &&dfs, int u) -> void {
sigma.push_back(u);
for (auto &[v, id] : adj[u]) {
if (vis[v]) continue;
vis[v] = true;
dfs(dfs, v);
sigma.push_back(u);
}
};
vis[1] = true;
dfs(dfs, 1);
// cerr << N sp sigma.size() << endl;
// for (auto &x : sigma) cerr << x << " ";
// cerr << endl;
vector<int> rizzler, loc(N+1, 0);
vector<bool> vis2(N+1);
for (auto &x : sigma) {
if (vis2[x]) rizzler.emplace_back(x);
else {
vis2[x] = true;
rizzler.emplace_back(x);
loc[x] = rizzler.size();
rizzler.emplace_back(x);
rizzler.emplace_back(x);
}
}
// cerr << N sp rizzler.size() << endl;
// for (auto &x : loc) cerr << x << " ";
// cerr << endl;
rizzler.pop_back();
int K = rizzler.size();
vector<vector<int>> ans(3*N, vector<int>(3*N, 1));
// cerr << "K" sp K << endl;
for (int i = 0; i < K; i++) {
// at +N
for (int j = 0; j < i+N; j++) {
if (j < 0 or j >= 3*N or N+i-j-1 < 0 or N+i-j-1 >= 3*N) continue;
ans[j][N+i-j-1] = rizzler[i];
}
}
vector<vector<bool>> vis3(N+1, vector<bool>(N+1));
for (int i = 1; i <= N; i++) {
int j = loc[i], k = (j+N > 3*N ? j-2*N : 0);
// cerr << j << endl;
for (auto &[v, id] : adj[i]) {
if (vis3[i][v]) continue;
vis3[i][v] = true;
// cerr << "put" sp v sp "at" sp k sp N+j-k-1 << endl;
if (0 <= k and k < 3*N and 0 <= N+j-k-1 and N+j-k-1 < 3*N)
ans[k][N+j-k-1] = v;
k++;
}
}
return ans;
}
