#include <bits/stdc++.h>
using namespace std;
vector<bool> done, visited;
int cl=0;
int sz;
vector<vector<int>> ans, adj;
void slf(int x){
for(int i = 0;i<sz;i++){
ans[cl][i]=x;
}
}
void sfad(int x){
slf(x);
for(int i = 0;i<adj[x].size();i++){
ans[cl][2*i]=adj[x][i];
}
}
void dfs(int n){
if(cl!=0){
slf(n);
cl++;
}
if(!done[n]){
sfad(n);cl++;
}
visited[n]=true;
for(auto thing:adj[n]){
if(!visited[thing]){
slf(n);cl++;
dfs(thing);
slf(n);cl++;
}
}
}
vector<vector<int>> create_map(int N, int M, vector<int> A, vector<int> B) {
sz=3*N;
adj.resize(N+1);
done.assign(N+1, false);
visited.assign(N+1, false);
for(int i = 0;i<M;i++){
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
ans.assign(3 * N, vector<int>(3 * N, 1));
dfs(1);
while(ans.size()>cl)ans.pop_back();
for(auto thing:ans)while(thing.size()>cl)thing.pop_back();
return ans;
}
