#include "worldmap.h" #include<bits/stdc++.h> using namespace std; int n, m; vector<int>a, b; namespace sub1{ vector<vector<int>>solve(){ vector<vector<int>>ans(n, vector<int>(n)); for(int i = 0; i < n; i++){ iota(ans[i].begin(), ans[i].end(), 1 + (i & 1)); } for(int i = 1; i < n; i += 2){ ans[i].back() = n - 1; } return ans; } } namespace sub2{ vector<vector<int>>solve(){ vector<vector<int>>g(n + 1); for(int i = 0; i < m; i++){ g[a[i]].push_back(b[i]); g[b[i]].push_back(a[i]); } vector<int>tour; function<void(int, int)>dfs; dfs = [&] (int s, int p){ tour.push_back(s); for(int& d : g[s]){ if(d != p){ dfs(d, s); tour.push_back(s); } } }; dfs(1, -1); int N = tour.size(); vector<vector<int>>ans(N, vector<int>(N)); for(int i = 0; i < N; i++){ iota(ans[i].begin(), ans[i].end(), i & 1); } for(int i = 1; i < N; i += 2){ ans[i].back() = 0; } for(int i = 0; i < N; i++){ for(int& j : ans[i]){ j = tour[j]; } } return ans; } } namespace sub3{ bitset<51>need[51]; vector<vector<int>>solve(){ vector<vector<int>>ans(n, vector<int>(n)); for(int i = ans[0][0] = 1; i <= n; i++){ need[i].set(); need[i][i] = false; } for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ if(i == 0 && j == 0){ continue; } bitset<51>avai; avai.reset(); if(j > 0){ avai |= need[ans[i][j - 1]]; } if(i > 0){ avai |= need[ans[i - 1][j]]; } bool flag = true; for(int k = 1; k <= n; k++){ if(avai[k]){ ans[i][j] = k; if(j > 0){ need[ans[i][j - 1]][k] = false; } if(i > 0){ need[ans[i - 1][j]][k] = false; } flag = false; break; } } if(flag){ int best = 1; for(int k = 2; k <= n; k++){ if(need[k].count() > need[best].count()){ best = k; } } ans[i][j] = best; } } } return ans; } } namespace sub4{ bool check_subtask(){ vector<bool>cnt(n + 1, false); cnt[0] = cnt[1] = true; for(int i = 0; i < m; i++){ if(min(a[i], b[i]) == 1){ cnt[a[i] ^ b[i] ^ 1] = true; } } return find(cnt.begin(), cnt.end(), false) == cnt.end(); } vector<vector<int>>solve(){ int N = n << 1; vector<vector<int>>ans(N, vector<int>(N, 1)); for(int i = 0, j = 0; i < N; i += 2){ for(int k = 0; k + 1 < N && j < m; k += 3, j++){ ans[i][k] = a[j]; ans[i][k + 1] = b[j]; } } return ans; } } namespace sub56{ vector<vector<int>>solve(){ vector<vector<int>>g(n + 1), f(n + 1); vector<vector<bool>>have(n + 1, vector<bool>(n + 1, false)); for(int i = 0; i < m; i++){ g[a[i]].push_back(b[i]); g[b[i]].push_back(a[i]); have[a[i]][b[i]] = have[b[i]][a[i]] = true; } vector<int>tour, par(n + 1, -1); int tdfs = par[1] = 0; function<void(int)>dfs; dfs = [&] (int s){ for(int x = par[s]; x != 0; x = par[x]){ f[s].push_back(x); f[s].push_back(x); } tour.push_back(s); for(int& d : g[s]){ if(d != par[s]){ if(par[d] == -1){ par[d] = s; dfs(d); tour.push_back(s); } } } for(int i = 2; i < f[s].size(); i += 2){ if(have[s][f[s][i]]){ if(i + 2 < f[f[s][i + 1] = s].size() && !have[s][f[s][i + 2]]){ f[s][i + 2] = f[s][i]; i += 2; } } } vector<int>temp((n << 1) - int(f[s].size()), s); f[s].insert(f[s].begin(), temp.begin(), temp.end()); }; dfs(1); vector<vector<int>>ans; for(int& i : tour){ ans.push_back(f[i]); } ans.push_back(ans.back()); return ans; } } vector<vector<int>>create_map(int __n, int __m, vector<int>__a, vector<int>__b){ swap(a, __a); swap(b, __b); if((m = __m) == (n = __n) - 1){ bool is_sub1 = true; for(int i = 0; i < m; i++){ if(a[i] != i + 1 || b[i] != i + 2){ is_sub1 = false; break; } } return is_sub1 ? sub1::solve() : sub2::solve(); } if((m << 1) == (n * (n + 1))){ return sub3::solve(); } if(sub4::check_subtask()){ return sub4::solve(); } return sub56::solve(); }