#include <bits/stdc++.h>
//#define int long long
#define pb push_back
#define fs first
#define sc second
using namespace std;
const int N = 45;
vector<int> adj[N], ord1, ord2;
bool adj1[N][N], vis[N];
int par[N];
void dfs(int v, int pr){
vis[v] = true;
par[v] = pr;
ord1.pb(v);
for(auto u:adj[v]){
if(!vis[u]){
dfs(u, v);
ord1.pb(v);
}
}
}
vector<vector<int>> create_map(int n, int m, vector<int> a, vector<int> b){
for(int i = 0; i < N; i++){
adj[i].clear();
vis[i] = false;
par[i] = -1;
}
ord1.clear();
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++) adj1[i][j] = 0;
for(int i = 0; i < m; i++){
adj[a[i]].pb(b[i]);
adj[b[i]].pb(a[i]);
adj1[a[i]][b[i]] = 1;
adj1[b[i]][a[i]] = 1;
}
dfs(1, 0);
vector<vector<int>> ans;
// for(int i = 1; i <= n; i++) cout << par[i] << " ";
// cout << endl;
// for(auto v:ord1) cout << v << " ";
// cout << endl;
ord1.pb(1);
for(int i = 0; i < ord1.size(); i++){
vector<int> f1, f2;
int nd = ord1[i];
while(nd != 0){
f1.pb(nd);
f1.pb(nd);
nd = par[nd];
}
// for(int j = 0; j < f1.size(); j++) cout << f1[j] << " ";
// cout << endl;
for(int j = 0; j < 2 * n - f1.size(); j++) f2.pb(ord1[i]);
for(int j = 0; j < f1.size(); j++) f2.pb(f1[j]);
f2.pb(0), f2.pb(0);
ans.pb(f2);
// for(int j = 0; j < f2.size(); j++){
// cout << f2[j] << " ";
// }
// cout << endl;
}
// for(int i = 0; i < 2 * n; i++){
// for(int j = 0; j < 2 * n; j++){
// cout << ans[i][j] << " ";
// }
// cout << endl;
// }
// for(int i = 0; i < 2 * n; i++) cout << ans[i].size() << " ";
// cout << endl;
for(int i = 0; i < 2 * n; i++){
int v = ord1[i], idx = 0;
while(ans[i][idx] == v or ans[i][idx] == par[v]){
idx++;
//if(i == 1) cout << "HERE" << endl;
}
//if(i == 1) cout << idx << " " << v << par[v] << endl;
for(int j = idx; j < 2 * n; j+=4){
if(!adj1[v][ans[i][j]]) continue;
if(!adj1[v][par[ans[i][j]]]){
ans[i][j + 1] = v;
ans[i][j + 2] = ans[i][j];
}else{
ans[i][j + 1] = v;
}
}
}
// for(int i = 0; i < 2 * n; i++){
// for(int j = 0; j < 2 * n; j++){
// cout << ans[i][j] << " ";
// }
// cout << endl;
// }
vector<vector<int>> ans1(2 * n, vector<int>(2 * n));
for(int i = 0; i < 2 * n; i++){
for(int j = 0; j < 2 * n; j++){
ans1[i][j] = ans[i][j];
}
}
return ans1;
}
// signed main(){
// vector<int> a = {1, 2, 2, 4, 5, 1, 2, 2, 4};
// vector<int> b = {2, 3, 4, 5, 6, 6, 5, 6, 6};
// vector<int> a1 = {1, 1, 2, 2, 3, 4, 5};
// vector<int> b1 = {3, 4, 3, 5, 6, 5, 6};
// vector<int> a2 = {1, 2};
// vector<int> b2 = {2, 3};
// vector<vector<int>> tari = create_map(3, 2, a2, b2);
// for(int i = 0; i < 6; i++){
// for(int j = 0; j < tari[i].size(); j++){
// cout << tari[i][j] << " ";
// }
// cout << endl;
// }
// }
