#include "worldmap.h"
#include <bits/stdc++.h>
#define F first
#define S second
#define lol ios::sync_with_stdio(false);cin.tie(NULL);
typedef long long ll;
typedef long double ld;
using namespace std;
const ll M = 998244353;
void dfs(vector<vector<ll>> &e, ll root, vector<bool> &vis, vector<ll> &tour) {
vis[root] = 1;
tour.push_back(root);
for(auto & v : e[root]) if(!vis[v]) {dfs(e, v, vis, tour); tour.push_back(root);}
}
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
vector<vector<ll>> e(N);
for(ll i=0; i<M; i++) {e[A[i]-1].push_back(B[i]-1); e[B[i]-1].push_back(A[i]-1);}
vector<bool> vis(N,0); vector<ll> tour;
dfs(e, 0, vis, tour);
vector<ll> sz, pos(N); vector<bool> used(N,0);
vector<ll> sum = {0};
for(auto & x : tour) {
sz.push_back(used[x] ? 1 : 3);
sum.push_back(sum.back()+ sz.back());
if(!used[x]) pos[x] = sum.back() - 2;
used[x] = 1;
}
vector<pair<ll,ll>> ord;
for(ll i=0; i<N; i++) ord.push_back(make_pair(min(pos[i], 4*N-pos[i]), i));
sort(ord.begin(), ord.end());
map<ll,ll> place;
for(ll i=0; i<N; i++) place[ord[i].S] = i;
vector<vector<ll>> ins(N);
for(ll i=0; i<M; i++) {
ll a = A[i]-1, b = B[i]-1;
if(place[a] > place[b]) swap(a,b);
ins[b].push_back(a);
}
vector<vector<int>> ans(2*N, vector<int>(2*N));
for(ll i=0; i<2*N-1; i++) {
for(ll j=sum[i]; j<sum[i+1]; j++) {
for(ll k=0; k<2*N; k++) if(j-k < 2*N && j-k >= 0) {
ans[k][j-k] = tour[i]+1;
}
}
}
for(ll i=0; i<N; i++) {
ll cnt = 0;
for(ll j=0; j<2*N; j++) if(pos[i] - j < 2*N && pos[i] - j >= 0) {
if(cnt < ins[i].size()) ans[j][pos[i] - j] = ins[i][cnt] + 1;
cnt++;
}
}
return ans;
}
