#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] = 0; } 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); ord1.pb(1); while((int)ord1.size() < 2 * n) ord1.pb(1); vector<vector<int>> ans; 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 < 2 * n - (int)f1.size(); j++) f2.pb(ord1[i]); for(int j = 0; j < (int)f1.size(); j++) f2.pb(f1[j]); f2.pb(0); f2.pb(0); while((int)f2.size() < 2 * n + 2) f2.pb(ord1[i]); ans.pb(f2); } for(int i = 0; i < 2 * n; i++){ int v = ord1[i]; int idx = 0; while(idx < (int)ans[i].size() and (ans[i][idx] == v or ans[i][idx] == par[v])) idx++; if(ans[i].empty() or ans[i][0] != v) continue; for(int j = idx; j + 1 < (int)ans[i].size() and j < 2 * n; j += 2){ int cur = ans[i][j]; if(cur <= 0 or cur >= N) continue; if(ans[i][j+1] != cur) continue; if(!adj1[v][cur]) continue; if(j + 2 >= (int)ans[i].size()){ ans[i][j + 1] = v; } else if(ans[i][j + 2] != cur and ans[i][j + 2] >= 0 and ans[i][j + 2] < N and adj1[ans[i][j + 2]][v]){ ans[i][j + 1] = v; } else { ans[i][j + 1] = v; ans[i][j + 2] = cur; } } } 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++){ int val = ans[i][j]; if(val == 0) val = 1; ans1[i][j] = val; } } 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<int> a3 = {1, 1, 2, 3}; // vector<int> b3 = {2, 3, 4, 4}; // vector<vector<int>> tari = create_map(4, 4, a3, b3); // for(int i = 0; i < 8; i++){ // for(int j = 0; j < 8; j++){ // cout << tari[i][j] << " "; // } // cout << endl; // } // }