#include "worldmap.h" #include <bits/stdc++.h> using namespace std; #define all(x) x.begin(), x.end() const int mxN = 42; vector<int> adj[mxN], waiting[mxN]; vector<int> ord; int parent[mxN], leaf[mxN]; int find(int u){ if(parent[u] == u) return u; return parent[u] = find(parent[u]); } bool unite(int u, int v){ u = find(u), v = find(v); if(u == v) return 0; parent[u] = v; return 1; } void dfs(int u = 1, int par = 0){ ord.push_back(u); int cnt = 0; for(auto it : adj[u]){ if(it ^ par) dfs(it, u), cnt += 1; } if(cnt == 0) leaf[u] = 1; ord.push_back(u); } void reset(int N){ ord.clear(); for(int i = 1; i <= N; ++i){ adj[i].clear(); waiting[i].clear(); parent[i] = i; leaf[i] = 0; } } vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) { reset(N); if(N == 1){ return {{1}}; } for(int i = 0; i < M; ++i){ if(unite(A[i], B[i])){ adj[A[i]].push_back(B[i]); adj[B[i]].push_back(A[i]); } waiting[A[i]].push_back(B[i]); waiting[B[i]].push_back(A[i]); } dfs(1, 0); vector<vector<int>> ans; int mx = 0; for(int i = 0; i < ord.size(); ++i){ if(leaf[ord[i]]) { leaf[ord[i]] = 0; continue; } vector<int> top_layer = {ord[i]}; vector<int> mid_layer; for(auto it : waiting[ord[i]]){ mid_layer.push_back(it); mid_layer.push_back(ord[i]); } mx = max(mx, (int) mid_layer.size()); ans.push_back(top_layer); if(mid_layer.size()) ans.push_back(mid_layer); ans.push_back(top_layer); } while(mx > ans.size()) ans.push_back(ans.back()); for(int i = 0; i < (int) ans.size(); ++i){ int x = ans[i][0]; if(ans[i].size() > 1) x = ans[i][1]; while((int) ans.size() > (int) ans[i].size()) { ans[i].push_back(x); } assert(ans.size() == ans[i].size()); } assert(ans.size() <= 240); return ans; }