#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]--;
graf[A[i]].pb(B[i]);
graf[B[i]].pb(A[i]);
}
vi usd(n);
vi par(n,-1);
auto dfs=[&](auto self,int v)->void{
usd[v]=1;
for(auto u:graf[v]){
if(usd[u]) continue;
par[u]=v;
self(self,u);
}
};
dfs(dfs,0);
rng(i,1,n) assert(par[i]!=-1);
const int n3=n*2.5;
vec<vi> grid;
int parity=0;
int visited=0;
auto rec=[&](auto self,int v)->void{
visited+=1;
if(sz(graf[v])){
vi row;
for(auto u:graf[v]){
if(!parity){
row.pb(v);
row.pb(u);
}else{
row.pb(u);
row.pb(v);
}
}
while(sz(row)<n3) row.pb(v);
grid.pb(row);
parity^=1;
}
for(auto u:graf[v]){
if(par[u]!=v) continue;
{
// print("e",v,u);
vi row;
rep(i,n){
if(!parity){
row.pb(v);
row.pb(u);
}else{
row.pb(u);
row.pb(v);
}
}
while(sz(row)<n3) row.pb(u);
grid.pb(row);
// parity^=1;
}
self(self,u);
if(visited<n){
vi row;
rep(i,n){
if(!parity){
row.pb(u);
row.pb(v);
}else{
row.pb(v);
row.pb(u);
}
}
while(sz(row)<n3) row.pb(v);
grid.pb(row);
// parity^=1;
}
}
};
rec(rec,0);
while(sz(grid)<n3){
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,2,2,3,3,3};
// vi b={2,3,4,3,4,4,5,6};
// map<pii,int> mp;
// rep(i,sz(a)){
// // print(a[i],b[i]);
// mp[minmax(a[i],b[i])]=1;
// }
// int n=6;
// 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);
// }
// }
// }
// }
