/*
______ _____ _______ _ _ _______ __ _ _____ _ _ _
|_____/ | | | |____/ |______ | \ | | | | | |
| \_ |_____| |_____ | \_ ______| | \_| |_____| |__|__|
. . . . . .
_\/ \/_ _\/ \/_ _\/ \/_
_\/\/_ _\/\/_ _\/\/_
_\_\_\/\/_/_/_ _\_\_\/\/_/_/_ _\_\_\/\/_/_/_
/ /_/\/\_\ \ / /_/\/\_\ \ / /_/\/\_\ \
_/\/\_ _/\/\_ _/\/\_
/\ /\ /\ /\ /\ /\
' ' ' ' ' '
*/
//#pragma GCC optimize("Ofast", "unroll-loops")
#include "bits/stdc++.h"
//#pragma GCC target("avx2")
//#pragma GCC target("lzcnt,popcnt")
using namespace std;
using ll = long long;
using bint = __int128;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)x.size()
#define ff first
#define ss second
#define rep(i, a, b) for (int i=a; i<(b); ++i)
#define rev(i, a, b) for (int i=b-1; i>=(a); --i)
template <class Fun>
class y_combinator_result {
Fun fun_;
public:
template <class T>
explicit y_combinator_result(T&& fun)
: fun_(std::forward<T>(fun)) {
}
template <class... Args>
decltype(auto) operator()(Args&&... args) {
return fun_(std::ref(*this), std::forward<Args>(args)...);
}
};
template <class Fun>
decltype(auto) y_combinator(Fun&& fun) {
return y_combinator_result<std::decay_t<Fun>>(std::forward<Fun>(fun));
}
string yon(ll ans) {
return ans ? "Yes" : "No";
}
template <typename T>
inline void ckmin(T& a, const T b) {
if (a > b)
a = b;
}
template <typename T>
inline void ckmax(T& a, const T b) {
if (a < b)
a = b;
}
inline double get_time() {
return std::chrono::duration_cast<std::chrono::milliseconds>(
std::chrono::system_clock::now().time_since_epoch())
.count();
}
ll popcnt(ll x){return __builtin_popcountll(x);}
ll popcnt_sgn(ll x){return (__builtin_parityll(x)&1 ? -1:1);}
ll topbit(ll x){return (x==0 ? -1:63-__builtin_clzll(x));}
ll lowbit(ll x){return (x==0 ? -1:__builtin_ctzll(x));}
//----------------------------------------------------------------------
vector<vector<int>> create_map(int n, int m, vector<int> a, vector<int> b){
if(n==1){
vector ans(1, vector<int>(1, 1));
return ans;
}
vector adj(n, vector<int>());
rep(i,0,m){
adj[a[i]-1].pb(b[i]-1);
adj[b[i]-1].pb(a[i]-1);
}
vector<int> order, vis(n, 0), pai(n, -1), depth(n), mxd(n, 0);
auto dfs=y_combinator([&](auto self, int s) -> void{
vis[s]=1;
for(int u: adj[s]) if(vis[u]==0){
pai[u]=s;
depth[u]=depth[s]+1;
mxd[u]=depth[u];
self(u);
ckmax(mxd[s], mxd[u]);
}
});
depth[0]=0;
dfs(0);
auto dfs2=y_combinator([&](auto self, int s) -> void{
order.pb(s);
vector<pair<int,int>> e;
for(int u: adj[s]) if(depth[u]==depth[s]+1) e.pb({mxd[u], u});
sort(all(e));
for(auto [_, u]: e){
self(u);
order.pb(s);
}
});
dfs2(0);
int k=2*n;
vector<vector<int>> linhas;
vis.assign(n, 0);
for(int u: order){
linhas.pb({u});
if(vis[u]==0){
vis[u]=1;
vector<int> l;
for(ll v: adj[u]) if(depth[v]<depth[u] && v!=pai[u]) l.pb(v);
if(sz(l)==0) l.pb(u);
linhas.pb(l);
linhas.pb({u});
}
}
assert(sz(linhas)==4*n-1);
vector ans(k, vector<int>(k, -1));
rep(i,0,4*n-1){
int ss=min(i+1, 4*n-i-1);
while(sz(linhas[i])<ss) linhas[i].pb(linhas[i].back());
rep(y,0,2*n){
int x=i-y;
if(x<0 || x>2*n-1) continue;
ans[x][y]=linhas[i].back();
linhas[i].pop_back();
}
}
rep(i,0,k) rep(j,0,k) ans[i][j]++;
return ans;
}
