#include <bits/stdc++.h>
#include "worldmap.h"
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define rng(i,c,n) for(int i=c;i<n;i++)
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
#define fi first
#define se second
#define vec vector
#define pb push_back
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
void print(){cout<<'\n';}
template<class H,class...T>
void print(const H&v,const T&...u){cout<<v<<' ',print(u...);}
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
int n=N;
int m=M;
vec<vi> graf(n);
rep(i,m){
A[i]--;
B[i]--;
// print(A[i],B[i]);
graf[A[i]].pb(B[i]);
graf[B[i]].pb(A[i]);
}
vi usd(n),par(n,-1),depth(n);
auto dfs=[&](auto self,int v)->void{
usd[v]=1;
for(auto u:graf[v]){
if(usd[u]) continue;
par[u]=v;
depth[u]=depth[v]+1;
self(self,u);
}
};
dfs(dfs,0);
// rng(i,1,n) print(par[i]);
rng(i,1,n) assert(par[i]!=-1);
const int n2=n*2;
vec<vi> grid;
vec<vi> f(n);
usd=vi(n);
auto has_back_edge=[&](int u,int v){
return find(all(graf[u]),v)!=graf[u].end() and par[v]!=u;
};
auto rec=[&](auto self,int v)->void{
usd[v]=1;
vi row;
if(v){
int up=par[v];
while(1){
row.pb(up);
row.pb(up);
if(!up) break;
up=par[up];
}
while(sz(row)<n2) row.insert(row.begin(),v);
int c=count(all(row),v);
for(int j=c;j<n2;j++){
if(has_back_edge(row[j],v)){
row[j+1]=v;
if(j+2<n2 and !has_back_edge(row[j+2],v)){
row[j+2]=row[j];
j+=3;
}else{
j++;
}
}
}
// print();
}else{
row=vi(n2,0);
}
f[v]=row;
grid.pb(row);
for(auto u:graf[v]){
if(par[u]!=v) continue;
self(self,u);
grid.pb(row);
}
};
rec(rec,0);
// if(sz(grid)>n2){
// cout<<"what\n";
// return grid;
// }
assert(sz(grid)<=n2);
while(sz(grid)<n2) grid.pb(grid.back());
const int si=sz(grid);
// print(sz(grid));
rep(i,si){
rep(j,si){
grid[i][j]+=1;
}
}
return grid;
}
// signed main(){
// vi a={1,1,1,4,5,4,6,7,7,6,8,8};
// vi b={2,3,4,5,6,6,7,5,4,8,1,5};
// map<pii,int> mp;
// rep(i,sz(a)){
// // print(a[i],b[i]);
// mp[minmax(a[i],b[i])]=1;
// }
// int n=max(*max_element(all(a)),*max_element(all(b)));
// int m=sz(a);
// auto grid=create_map(n,m,a,b);
// const int si=sz(grid);
// rep(i,si){
// // assert(sz(grid[i])==si);
// for(auto x:grid[i]) cout<<x<<" ";
// cout<<"\n";
// }
// auto check=[&](int i,int j,int i1,int j1){
// int x=grid[i][j];
// int y=grid[i1][j1];
// if(x==y){
// return;
// }
// // print(x,y);
// assert(mp.find(minmax(x,y))!=mp.end());
// };
// rep(i,si){
// rep(j,si){
// if(i+1<si){
// check(i,j,i+1,j);
// }
// if(j+1<si){
// check(i,j,i,j+1);
// }
// }
// }
// }
