这部分的构造就是先考虑树，很容易按照子树来分类，使用父亲来间隔各个儿子，然后递归处理儿子进行就行了。
```
u v1 u v2 u
u v1 u v2 u
u v1 u v2 u
```
扩展到一般图，同理考虑 dfs 树，会产生返祖边。我们可以单独开一列表示一些能上来的孙子节点，中间用 $u$ 来隔开。这么做是 $4n\times 2n$ 的。
```
u v1 u v2 u c1 u
u v1 u v2 u u u
u v1 u v2 u c2 u
```
其实信息量是 $8n^2<3n\times 3n$，但是为了凑成正方形不得不变成 $4n\times 4n$。所以考虑均匀分布，返祖边信息还是竖着来，这个时候我们发现儿子信息其实可以并列地放在若干行内。原因是行的高度约束是 $2\times$ 子树大小，而儿子子树大小求和刚好是父亲子树大小量级，所以你可以这么塞进去。这么做的意义是我们把原先列之间的 $u$ 间隔放到了行中，减少了列数。这么做是 $3n\times 2n$ 的，有 $86\rm pts$。
```
u u u u u
u c1 u v1 v1
u u u u u
u c2 u v1 v1
u u u u u
```
略加优化就可以满分了，你会发现下图中的问号位置并不需要填入 $u$，于是你在相邻两层镶嵌插入就可以减少一个 $n$ 的宽度了。
```
? u ? u u
u c1 u v1 v1
? u u u u
u c2 u v1 v1
? u ? u u
```
```cpp
#include<bits/stdc++.h>
#define pb emplace_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const int maxn=300;
void cmax(int &x,int y){ x=x>y?x:y; }
void cmin(int &x,int y){ x=x<y?x:y; }
int n,m,dfn[maxn],e[maxn][maxn],sz[maxn],rev[maxn];
vector<int> G[maxn],son[maxn]; int tot=0;
vector<vi> emp,ans;
void Clear(){
for(int i=1;i<=n;i++){
G[i].clear(); son[i].clear();
dfn[i]=sz[i]=rev[i]=0;
for(int j=1;j<=n;j++) e[i][j]=0;
} tot=0;
}
void dfs(int u){
sz[u]=1; dfn[u]=++tot; rev[tot]=u;
for(auto v:G[u]){
if(dfn[v]) continue;
dfs(v); sz[u]+=sz[v];
son[u].pb(v);
}
}
vi merge(vi L,vi R){ for(auto z:R) L.pb(z); return L; }
vector<vi> solve(int u,int len){
if(!son[u].size()) return emp;
vector<vi> res,cur; vi s,tt(1,u);
for(int i=dfn[u]+1;i<=dfn[u]+sz[u]-1;i++){
int v=rev[i];
if(e[u][v]) s.pb(v);
}
res.resize(2*s.size());
if(u==1) for(auto &z:res) z.pb(u);
for(int i=0;i<s.size();i++){//交替放置 u s[i]
res[2*i].pb(u);
res[2*i+1].pb(s[i]);
}
for(auto &z:res)
if(z.back()!=u) z.pb(u);//外层封住 s[i]
int j=1,flag=0;//第一行空着
if(u==1) tt.pb(u);
for(auto v:son[u]){
cur=solve(v,len-2-(u==1));
if(!cur.size()) continue;
flag=1;
while(j+cur.size()+1>res.size()) res.pb(tt);
if(res[j+1].size()>=2+(u==1)) j++;
for(auto z:cur){
if(res[j].size()<2+(u==1)) res[j].pb(v);
res[j]=merge(res[j],z); j++;
}
res[j++].pb(u);
}
flag=1;
for(auto id:res.back())
if(id!=u) flag=0;
if(!flag) res.pb(tt);//封底
for(auto &z:res)//补满
while(z.size()<len) z.pb(z.back());
return res;
}
vector<vi> create_map(int N,int M,vi A,vi B){
n=N; m=M; ans.clear();
if(n==1){
vi tmp; tmp.pb(1);
ans.pb(tmp); return ans;
}
for(int i=0;i<m;i++){
e[A[i]][B[i]]=e[B[i]][A[i]]=1;
G[A[i]].pb(B[i]),G[B[i]].pb(A[i]);
}
dfs(1); ans=solve(1,2*n);
vi base=ans.back();
while(ans.size()<2*n) ans.pb(base);
Clear(); return ans;
}
```