#include "worldmap.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define fi first
#define se second
typedef long long ll;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnf(2106);
const int N = 250;
int n;
vector<int> g[N];
bool c[N];
vector<int> gg[N];
void dfs(int x, vector<int>& v)
{
c[x] = true;
v.push_back(x);
for (int i = 0; i < g[x].size(); ++i)
{
int h = g[x][i];
if (!c[h])
{
dfs(h, v);
v.push_back(-x);
}
else
gg[x].push_back(h);
}
}
vector<pair<int, int> > u[N * 8];
std::vector<std::vector<int> > create_map(int N, int M, std::vector<int> A, std::vector<int> B)
{
n = N;
/*{
int t = n * 2;
vector<int> v;
for (int s = 0; s <= t * 2; ++s)
{
int q = 0;
for (int i = 0; i < t; ++i)
{
for (int j = 0; j < t; ++j)
{
if (i + j == s)
{
++q;
v.push_back(q);
}
}
}
}
reverse(all(v));
for (int i = 0; i < n; ++i)
{
int y = i;
while (1)
{
if (v.empty())
{
cout << "WA\n";
exit(0);
}
int x = v.back();
v.pop_back();
if (x >= y)
break;
y -= x;
}
}
cout << "OK\n";
exit(0);
}*/
for (int i = 0; i < N * 8; ++i)
u[i].clear();
int m = n * 3;
for (int i = 0; i < m; ++i)
for (int j = 0; j < m; ++j)
u[i + j].push_back(m_p(i, j));
for (int i = 0; i <= n + 1; ++i)
{
g[i].clear();
gg[i].clear();
c[i] = false;
}
for (int i = 0; i < M; ++i)
{
int x = A[i];
int y = B[i];
g[x].push_back(y);
g[y].push_back(x);
}
vector<int> v;
dfs(1, v);
for (int x = 1; x <= n; ++x)
assert(c[x]);
vector<vector<int> > ans(m, vector<int>(m, 0));
int s = 0;
for (int i = 0; i < sz(v); ++i)
{
int x = v[i];
if (x > 0)
{
for (int j = 0; j < sz(u[s]); ++j)
{
int ii = u[s][j].fi;
int jj = u[s][j].se;
ans[ii][jj] = x;
}
++s;
while (!gg[x].empty())
{
for (int j = 0; j < sz(u[s]); ++j)
{
int ii = u[s][j].fi;
int jj = u[s][j].se;
if (!gg[x].empty())
{
ans[ii][jj] = gg[x].back();
gg[x].pop_back();
}
else
ans[ii][jj] = x;
}
++s;
for (int j = 0; j < sz(u[s]); ++j)
{
int ii = u[s][j].fi;
int jj = u[s][j].se;
ans[ii][jj] = x;
}
++s;
}
}
else
{
x *= -1;
for (int j = 0; j < sz(u[s]); ++j)
{
int ii = u[s][j].fi;
int jj = u[s][j].se;
ans[ii][jj] = x;
}
++s;
}
}
for (int i = 0; i < m; ++i)
{
for (int j = 0; j < m; ++j)
{
if (ans[i][j] == 0)
ans[i][j] = abs(v.back());
}
}
/*for (int i = 0; i < sz(v); ++i)
{
int x = v[i];
if (x > 0)
{
vector<int> t(2 * n, x);
ans.push_back(t);
for (int i = 0; i < g[x].size(); ++i)
t[i * 2] = g[x][i];
ans.push_back(t);
t.assign(2 * n, x);
ans.push_back(t);
}
else
{
x *= -1;
vector<int> t(2 * n, x);
ans.push_back(t);
}
}
for (int i = 0; i < sz(ans); ++i)
assert(sz(ans[i]) == sz(ans[0]));
while (sz(ans) < sz(ans[0]))
{
ans.push_back(ans.back());
}
while (sz(ans[0]) < sz(ans))
{
for (int i = 0; i < sz(ans); ++i)
ans[i].push_back(ans[i].back());
}*/
return ans;
}
/*
1
20 0
2
3 2
1 2
2 3
4 4
1 2
1 3
2 4
3 4
*/
