#include <bits/stdc++.h>
using namespace std;
const int K=240;
vector<vector<int>> adj, g;
int j;
set<pair<int,int>> s;
void dfs(int u){
for(int i=0;i<K;i++){
g[i][j]=u;
}
j++;
for(int i=0;i<(int)adj[u].size();i++){
int v=adj[u][i];
if(s.count({u,v})||s.count({v,u}))continue;
for(int i=0;i<K;i++){
g[i][j]=v;
}
j++;
s.insert({u,v});s.insert({v,u});
dfs(v);
for(int i=0;i<K;i++){
g[i][j]=u;
}
j++;
}
}
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B){
j=0;
adj.resize(0);
g.resize(0);
s.clear();
g.resize(K, vector<int> (K, -1));
adj.resize(N+1);
for(int i=0;i<M;i++){
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
dfs(1);
int lim=-1;
for(int i=0;i<K;i++){
for(int j0=0;j0<K;j0++){
lim=j0;
if(g[i][j0]==-1){
break;
}
}
if(lim!=-1)break;
}
vector<vector<int>> res(lim, vector<int>(lim));
for(int i=0;i<lim;i++){
for(int j=0;j<lim;j++){
res[i][j]=g[i][j];
}
}
return res;
}
