#include <bits/stdc++.h>
#include "worldmap.h"
using namespace std;
#define st first
#define nd second
#define pb push_back
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define irep(i,a,b) for(int i = a; i >= b; i--)
typedef long long ll;
typedef long double ld;
//typedef __int128 int128;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef pair<double,double> pd;
typedef pair<ll,ll> pl;
const int max_n = 50;
vi g[max_n];
int h[max_n];
int s[max_n];
//bool leaf[max_n];
int arr[max_n*3][max_n*3];
void set_tree(int v){
//cout << "set_tree, v: " << v << " h: " << h[v] << '\n';
s[v] = 1;
//leaf[v] = 1;
for(auto x:g[v]){
//cout << "v: " << v << " x: " << x << '\n';
if(h[x]) continue;
//leaf[v] = 0;
h[x] = h[v]+1;
set_tree(x);
s[v] += s[x];
}
//cout << "v: " << v << " s: " << s[v] << '\n';
}
void solve(int v, int i, int j){
/* if(leaf[v]){
cout << "leaf\n";
return;
} */
int end = j+3*s[v]-2; //raz -1 bierzemy od size-1 jako placeholder!
//cout << "\nsolve od v: " << v << " i: " << i << " j: " << j << " end: " << end << '\n';
rep(it,j,end) arr[i][it] = v; //pierwszy rzad same 1!
//tutaj placeholder niepotrzebne!
int l = j+1;
for(auto x:g[v]){
if(h[x] < h[v]) continue; //nie dajemy kolejnych
arr[i+1][l] = x; arr[i+1][l+1] = v;
l += 2;
}
arr[i+1][j] = v;
rep(it,l,end) arr[i+1][it] = v;
rep(it,j,end) arr[i+2][it] = v; //ostatni to samo!
//teraz solve na kolejne :)
//tutaj placeholder!
arr[i+3][j] = v; //ten najbardziej po lewo!
l = j+1; //nastepne od ktorego zaczynamy
for(auto x:g[v]){
if(h[x] != h[v]+1) continue;
solve(x,i+3,l);
l += 3*s[x];
arr[i+3][l-1] = v;
}
rep(it,l,j) arr[i+3][it] = v;
}
vector<vi> create_map(int n, int m, vi a, vi b){
//na 86 :)
rep(i,0,m-1){
int x = a[i]; int y = b[i];
g[x].pb(y); g[y].pb(x);
//cout << "set_g, x: " << x << " y: " << y << '\n';
}
h[1] = 1;
set_tree(1);
solve(1,1,1);
rep(i,1,3*n)
rep(j,1,3*n){
if(arr[i][j]) continue;
if(i == 1) arr[i][j] = 1;
else arr[i][j] = arr[i-1][j];
}
vector<vi> ans;
rep(i,1,3*n){
vi v;
rep(j,1,3*n) v.pb(arr[i][j]);
ans.pb(v);
}
rep(i,1,n){
g[i].clear();
h[i] = 0;
s[i] = 0;
}
rep(i,1,3*n) rep(j,1,3*n) arr[i][j] = 0;
return ans;
}
