#include "worldmap.h"
#include<bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define int long long
#define vi vector<int>
#define vvi vector<vector<int>>
#define pii pair<int, int>
#define vpii vector<pair<int, int>>
#define vc vector<char>
#define vb vector<bool>
#define mii map<int,int>
#define f0r(i,n) for(int i=0;i<n;i++)
#define FOR(i,k,n) for(int i=k;i<n;i++)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define in(a) int a; cin>>a
#define in2(a,b) int a,b; cin>>a>>b
#define in3(a,b,c) int a,b,c; cin>>a>>b>>c
#define in4(a,b,c,d) int a,b,c,d; cin>>a>>b>>c>>d
#define vin(v,n); vi v(n); f0r(i,n){cin>>v[i];}
#define out(a) cout<<a<<'\n'
#define out2(a,b) cout<<a<<' '<<b<<'\n'
#define out3(a,b,c) cout<<a<<' '<<b<<' '<<c<<'\n'
#define out4(a,b,c,d) cout<<a<<' '<<b<<' '<<c<<' '<<d<<'\n'
#define pout(a) cout<<a.first<<' '<<a.second<<'\n'
#define vout(v) for(auto u : v){cout<<u<<' ';} cout<<endl
#define dout(a) cout<<a<<' '<<#a<<endl
#define dout2(a,b) cout<<a<<' '<<#a<<' '<<b<<' '<<#b<<endl
#define yn(x); if(x){cout<<"YES"<<'\n';}else{cout<<"NO"<<'\n';}
const int leg = 1e9 + 7;
const int mod = 998244353;
using namespace std;
const int mxn = 45;
vvi adj(mxn), edj(mxn);
vi euler_tour;
struct DSU{
int n; vi par, sz;
DSU(int N){
n = N; par.resize(n); sz.resize(n);
f0r(i, n)par[i]=i,sz[i]=1;
}
int find(int x){
if(par[x] == x)return x;
return par[x] = find(par[x]);
}
void unite(int a, int b){
a = find(a); b = find(b);
if(sz[a] < sz[b])swap(a,b);
sz[a] += sz[b]; par[b] = a;
}
};
void dfs(int node, int from){
euler_tour.pb(node);
for(auto u : edj[node]){
if(u != from)dfs(u, node), euler_tour.pb(node);
}
}
std::vector<std::vector<signed>> create_map(signed N, signed M, std::vector<signed> A, std::vector<signed> B) {
std::vector<std::vector<signed>> grid(2 * N, std::vector<signed>(2 * N, 1));
f0r(i, N+1){
adj[i].clear(); edj[i].clear();
}
euler_tour.clear();
vector<vpii>diags(4 * N - 1);
vvi pending(N+1);
f0r(i, 2 * N){
f0r(j, 2 * N){
diags[i + j].pb(mp(i,j));
}
}
f0r(i, M){
adj[A[i]].pb(B[i]); adj[B[i]].pb(A[i]);
}
DSU d = DSU(N+1);
f0r(i, M){
int x = A[i]; int y = B[i];
if(d.find(x) != d.find(y)){
d.unite(x,y); edj[x].pb(y); edj[y].pb(x);
}
}
vector<vb>done(N+1, vb(N+1));
vvi ans;
vb vis(N+1);
dfs(1,-1);
int ptr = 0;
f0r(i, N+1){
for(auto u : edj[i]){
done[i][u] = 1; done[u][i] = 1;
}
// vout(edj[i]);
}
f0r(i, N+1){
sort(all(adj[i]));
}
vi diag_name(N+1);
vi diag_length(N+1);
for(auto v : euler_tour){
if(!vis[v]){
vi tmp;
f0r(i, diags[ptr].size())tmp.pb(v);
ans.pb(tmp);
ptr++;
vi t2;
/*
for(auto x : pending[v]){
t2.pb(x);
done[v][x] = 1; done[x][v] = 1;
}
if(v == 1){
// vout(t2);
}
for(auto u : adj[v]){
if(t2.size() >= diags[ptr].size())break;
if(!done[u][v]){
done[u][v] = 1; done[v][u] = 1;
t2.pb(u);
}
}
if(v == 1){
// vout(t2);
}
for(auto u : adj[v]){
if(!done[u][v]){
pending[u].pb(v);
}
}
if(t2.empty())t2.pb(v);
*/
diag_name[v] = ptr;
diag_length[v] = diags[ptr].size();
ans.pb(t2);
ptr++;
vi t3;
f0r(i, diags[ptr].size())t3.pb(v);
ans.pb(t3);
ptr++;
vis[v] = 1;
}
else{
vi tmp;
f0r(i, N)tmp.pb(v);
ans.pb(tmp);
ptr++;
}
}
f0r(i, ans.size()){
// vout(ans[i]);
}
vpii ord;
FOR(i,1,N+1){
ord.pb(mp(diag_length[i], i));
}
sort(all(ord));
f0r(i, ord.size()){
int v = ord[i].second;
int l = ord[i].first;
vi tmp;
vpii nxt;
for(auto u : adj[v]){
nxt.pb(mp(diag_length[u], u));
}
sort(all(nxt));
for(auto [d, u] : nxt){
if(tmp.size() == l)break;
if(!done[u][v]){
done[u][v] = 1; done[v][u] = 1;
tmp.pb(u);
}
}
if(tmp.size() == 0)tmp.pb(v);
ans[diag_name[v]] = tmp;
}
// vout(euler_tour);
int p1 = 0;
// dout(ans.size());
f0r(i, 4 * N - 1){
// if(diags[i].size() >= N){
if(p1 < ans.size()){
int p2 = 0;
for(auto [x,y] : diags[i]){
if(p2 == ans[p1].size()){
grid[x][y] = ans[p1][p2-1];
}
else{
grid[x][y] = ans[p1][p2];
p2++;
}
}
p1++;
}
// }
}
f0r(i, ans.size()){
// vout(ans[i]);
}
return grid;
}
