#include "worldmap.h"
#define pb push_back
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 10;
int n, m;
vector < int > g[maxn];
int tmr, a[maxn];
int seen[maxn], label[maxn], is_label[maxn];
void dfs(int beg, int from)
{
seen[beg] = 1;
cout << beg << " anddd from " << from << endl;
tmr ++;
a[tmr] = beg;
label[beg] = tmr;
is_label[tmr] = 1;
for (auto nb: g[beg])
{
if(nb == from)
continue;
if(seen[nb] == 1)continue;
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;
for (int i = 0; i < m; ++ i)
{
int from = A[i], to = B[i];
g[from].pb(to);
g[to].pb(from);
}
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;
for (int i = 1; i <= tmr; ++ i)
{
on ++;
type[on] = 1;
col[on] = a[i];
if(is_label[i] == 1)
{
on ++;
type[on] = 2;
col[on] = a[i];
space[a[i]] = sz[on];
on ++;
type[on] = 1;
col[on] = a[i];
}
}
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: g[x])
{
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 < take[cvqt].size()-1)j ++;
}
}
last = cvqt;
}
return ans;
}
