#include <bits/stdc++.h>
using namespace std;
vector<int> v[41];
vector<vector<int>> va2;
int i, j, d, n, m, va[125][125];
bool c, ch[41], cn[41][41];
void dfs(int cu, int pa){
ch[cu] = 1;
if(c == 0){
for( j = 2; j <= 2*n; j+=2) va[d][j] = cu;
for( j = 1; j <= 2*n; j+=2){
va[d-1][j] = cu; va[d+1][j] = cu;
if(cn[cu][j/2+1]) va[d][j] = j/2+1;
} cout << '\n';
}
else{
for( j = 1; j <= 2*n+1; j+=2) va[d][j] = cu;
for( j = 2; j <= 2*n; j+=2){
va[d-1][j] = cu; va[d+1][j] = cu;
if(cn[cu][j/2]) va[d][j] = j/2;
}
}
c = 1-c; d += 2;
for(int z: v[cu]){
if(ch[z] == 1) continue;
dfs(z, cu);
if(c == 0){
for( j = 2; j <= 2*n; j+=2) va[d][j] = cu;
for( j = 1; j <= 2*n; j+=2) va[d-1][j] = cu;
}
else{
for( j = 1; j <= 2*n; j+=2) va[d][j] = cu;
for( j = 2; j <= 2*n; j+=2) va[d-1][j] = cu;
}
d++;
}
}
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) {
n = N; m = M;
for( i = 1; i <= n; i++){ ch[i] = 0;
for( j = 1; j <= n; j++) cn[i][j] = 0;
}
for( i = 0; i < m; i++) v[A[i]].push_back(B[i]), v[B[i]].push_back(A[i]), cn[A[i]][B[i]] = 1, cn[B[i]][A[i]] = 1;
va2.resize(3*n);
for( i = 0; i < 3*n; i++) va2[i].resize(3*n);
for( i = 1; i <= 3*n; i++){
for( j = 1; j <= 3*n; j++) va[i][j] = 0;
}
d = 1; c = 0; dfs(1, -1);
for( i = 1; i <= 3*n; i++){
for( j = 1; j <= 3*n; j++) if(va[i][j] == 0) va[i][j] = va[i][j-1];
}
for( j = 1; j <= 3*n; j++){
for( i = 1; i <= 3*n; i++) if(va[i][j] == 0) va[i][j] = va[i-1][j];
}
for( j = 1; j <= 3*n; j++){
for( i = 1; i <= 3*n; i++) va2[i-1][j-1] = va[i][j];
}
for( i = 1; i <= n; i++) v[i].clear();
return va2;
}
