#include<bits/stdc++.h> using namespace std; #define ff first #define ss second #define pb push_back vector<int>adj[50]; vector<int>rt; bool vis[100]; void dfs(int a){ vis[a]=1; rt.pb(a); vector<pair<int,int>>vc; for(auto b:adj[a]){ vc.pb({(int)adj[b].size(),b}); } sort(vc.begin(),vc.end()); adj[a].clear(); for(auto p:vc){ adj[a].pb(p.ss); } for(auto b:adj[a]){ if(vis[b])continue; dfs(b); rt.pb(a); } } std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B) { for(int i=1;i<=N;i++){ adj[i].clear(); } for(int i=0;i<M;i++){ adj[A[i]].pb(B[i]); adj[B[i]].pb(A[i]); } rt.clear(); pair<int,int>p={INT_MAX,0}; for(int i=1;i<=N;i++){ vis[i]=0; p=min(p,{(int)adj[i].size(),i}); } dfs(p.ff); reverse(rt.begin(),rt.end()); int h=N*3; vector< vector< int> > v(h, vector<int> (h)); for(int i=0;i<h;i++){ for(int j=0;j<h;j++)v[i][j]=p.ff; } for(int i=0;i<rt.size();i++){ int x=i*3; for(int j=0;j<=min(x,h-1);j++){ int k=x-j; if(k>h-1)continue; v[j][k]=rt[i]; } x=i*3+2; for(int j=0;j<=min(x,h-1);j++){ int k=x-j; if(k>h-1)continue; v[j][k]=rt[i]; } x=i*3+1; for(int j=0;j<=min(x,h-1);j++){ int k=x-j; if(k>h-1)continue; v[j][k]=rt[i]; } vector<pair<int,int>>del; for(int j=0;j<=min(x,h-1);j++){ int k=x-j; if(k>h-1)continue; int a=rt[i]; if(j<adj[a].size()){ v[j][k]=adj[a][j]; del.pb({a,adj[a][j]}); } } for(auto p:del){ erase(adj[p.ff],p.ss); erase(adj[p.ss],p.ff); } } return v; }