#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define F first
#define S second
vector<vector<int>> ans, kl;
queue<int> h; vector<char> vis;
void dfs(int u)
{
vis[u]=1; h.push(u);
for(auto x: kl[u]){if(vis[x])continue; dfs(x); h.push(u);}
}
vector<vector<int>> create_map(int n, int m, vector<int> a, vector<int> b) {
kl.assign(n+1, vector<int>()); vector<int> o(n+1, 0);
vis.assign(n+1, 0);
for(ll i=0; i<m; i++){kl[a[i]].push_back(b[i]); kl[b[i]].push_back(a[i]);}
for(int i=1; i<=n; i++){sort(kl[i].begin(), kl[i].end());}
for(int i=1; i<=n; i++){if(!vis[i])dfs(i);}
int y=(h.size())+2*n; ans.assign(3*n, vector<int>(3*n, -1)); int j=0;
vector<vector<int>> di; vector<vector<pair<int, int>>> t(n+1);
vector<vector<bool>> v(n+1, vector<bool>(n+1, 0));
while(!h.empty())
{
int u=h.front(); h.pop(); vector<int> g(y, u); di.push_back(g);
if(o[u]==0)
{
vector<int> p(y, u);int i=1, xd=di.size();
for(auto x: kl[u]){if(i>=y)break; t[u].push_back({xd, i}); i+=2;}
di.push_back(p); vector<int> l(y, u);di.push_back(l);
}
o[u]++;
}
for(int i=1; i<=n; i++)
{
for(auto x: kl[i])
{
if(v[i][x])continue;
v[i][x]=1; v[x][i]=1; if(t[x].empty())continue;
di[t[x].back().F][t[x].back().S]=i; t[x].pop_back();
}
}
for(int i=0; i<min((int)di.size(), 4*n); i++)
{
for(int j=0; j<3*n; j++){if(i-j>=0&&i-j<3*n)ans[j][i-j]=di[i][j];}
}
return ans;
}
