#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 dx[4] = {1, -1, 0, 0}; int dy[4] = {0, 0, 1, -1}; 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){ for(auto it : adj[u]){ if(it ^ par) { ord.push_back(u); dfs(it, u); } } if(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); vector<vector<bool>> mat(N + 5, vector<bool> (N + 5, 0)); 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]); mat[A[i]][B[i]] = 1; mat[B[i]][A[i]] = 1; mat[A[i]][A[i]] = 1; mat[B[i]][B[i]] = 1; } 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); reset(N); for(int i = 0; i < (int) ans.size(); ++i){ assert(ans.size() == ans[i].size()); for(int j = 0; j < (int) ans[i].size(); ++j){ for(int k = 0; k < 4; ++k){ int ni = i + dx[k], nj = j + dy[k]; if(min(ni, nj) >= 0 && max(ni, nj) < (int) ans.size()){ assert(ans[i][j] <= N && ans[i][j] >= 1); assert(ans[ni][nj] <= N && ans[ni][nj] >= 1); if(ans[i][j] != ans[ni][nj]) { //assert(); //cout << i << " " << j << "\n"; if(!mat[ans[i][j]][ans[ni][nj]]) cout << i << " " << j << "\n"; } } } } } return ans; }