#include "bits/stdc++.h"
#include "worldmap.h"
using namespace std;
const int sz = 1e6 + 9;
vector<vector<int>> ans;
vector<vector<int>> v;
bitset<sz> bs;
int r;
void color(int c)
{
for (int i = 0; i < (int)ans[r].size(); ++i)
{
if (!ans[r][i])
{
ans[r][i] = c;
}
}
++r;
}
bool dfs(int node)
{
if (bs[node] == 1)
{
return false;
}
bs[node] = 1;
color(node);
for (int i = 0; i < (int)v[node].size(); ++i)
{
ans[r][i << 1LL] = v[node][i];
}
color(node);
color(node);
for (auto to : v[node])
{
if (dfs(to))
{
color(node);
}
}
return true;
}
vector<vector<int>> create_map(int n, int m, vector<int> a, vector<int> b)
{
ans.assign(n << 2LL, vector<int>(n << 2LL, 0LL));
v.assign(n + 1, vector<int>());
for (int i = 0; i <= 1e6; ++i)
{
bs[i] = 0;
}
for (int i = 0; i < m; ++i)
{
v[a[i]].push_back(b[i]);
v[b[i]].push_back(a[i]);
}
r = 0l;
dfs(1);
while(r < (int)ans.size())
{
color(ans[r - 1][0]);
}
return ans;
}
