#include "worldmap.h"
#define pb push_back
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 10;
int n, m;
vector < pair < int, int > > g[maxn];
int tmr, a[maxn];
int seen[maxn], label[maxn], is_label[maxn];
int noneed[maxn];
void dfs(int beg, int from)
{
seen[beg] = 1;
tmr ++;
a[tmr] = beg;
label[beg] = tmr;
is_label[tmr] = 1;
for (auto &[nb, i]: g[beg])
{
if(nb == from)
continue;
if(seen[nb] == 1)continue;
noneed[i] = 1;
dfs(nb, beg);
tmr ++;
a[tmr] = beg;
}
}
unordered_map < int, int > mp;
int diff[maxn * 4], sz[maxn * 4];
int diag[maxn * 4];
int type[maxn * 4], col[maxn * 4], space[maxn * 4];
bool cmp(int col1, int col2)
{
if(space[col1] < space[col2])return true;
return false;
}
int used[maxn];
vector < int > take[maxn];
vector < pair <int, int > > cells[maxn * 4];
std::vector<std::vector<int>> create_map(int N, int M, std::vector<int> A, std::vector<int> B)
{
n = N;
m = M;
mp.clear();
for (int i = 0; i <= n; ++ i)
{
g[i].clear();
take[i].clear();
used[i] = 0;
seen[i] = 0;
}
for (int i = 1; i <= 15*n; ++ i)
{
cells[i].clear();
diff[i] = 0;
sz[i] = 0;
diag[i] = 0;
type[i] = 0;
sz[i] = 0;
space[i] = 0;
col[i] = 0;
}
for (int i = 0; i < m; ++ i)
{
noneed[i] = 0;
int from = A[i], to = B[i];
g[from].pb(make_pair(to, i));
g[to].pb(make_pair(from, i));
}
tmr = 0;
for (int i = 1; i <= tmr; ++ i)
{
seen[i] = 0;
is_label[i] = 0;
a[i] = 0;
label[i] = 0;
}
dfs(1, -1);
int r = 0;
int currsz = 1;
for (int i = -2*n+1; i < 2*n; ++ i)
{
r ++;
diff[r] = i;
mp[i] = r;
sz[r] = currsz;
if(i < 0)
currsz ++;
else
currsz --;
}
int on = 0;
// cout << " !! " << endl;
int cnt = 0;
for (int i = 1; i <= tmr; ++ i)
{
//cout << a[i] << " ,, ";
on ++;
type[on] = 1;
col[on] = a[i];
if(is_label[i] == 1)
{
cnt ++;
if(cnt > 2)
{on ++;
type[on] = 2;
col[on] = a[i];
space[a[i]] = sz[on];
on ++;
type[on] = 1;
col[on] = a[i];
}
}
}
assert(on <= r);
// cout << endl;
vector < int > u;
for (int i = 1; i <= n; ++ i)
u.pb(i);
sort(u.begin(), u.end(), cmp);
for (auto x: u)
{
used[x] = 1;
for (auto &[nb, i]: g[x])
{
if(noneed[i])continue;
if(used[nb])take[x].pb(nb);
}
take[x].pb(x);
}
for (int i = 0; i < 2*n; ++ i)
{
for (int j = 0; j < 2*n; ++ j)
{
int diff = i - j;
int diag = mp[diff];
cells[diag].pb(make_pair(i, j));
}
}
std::vector<std::vector<int>> ans(2 * n, std::vector<int>(2*n, 1));
int last = 0;
for (int i = 1; i <= r; ++ i)
{
int cvqt = col[i];
if(cvqt == 0)cvqt = last;
if(type[i] != 2)
{
for (auto x: cells[i])
ans[x.first][x.second] = cvqt;
}
else
{
int j = 0;
for(auto x: cells[i])
{
ans[x.first][x.second] = take[cvqt][j];
if(j < (int)(take[cvqt].size()-1))j ++;
}
// assert(j > take[cvqt].size() - 2);
}
last = cvqt;
}
return ans;
}
