#include "parks.h"
#include<bits/stdc++.h>
using namespace std;
int n;
struct DSU
{
int father[200005],siz[200005];
void init()
{
for(int i=0;i<n;i++)
father[i]=i, siz[i]=1;
}
int get(int x)
{
if(father[x]!=x)
father[x]=get(father[x]);
return father[x];
}
void unite(int x, int y)
{
x = get(x);
y = get(y);
if(x==y)
return;
if(siz[x] < siz[y])
swap(x,y);
siz[x] += siz[y];
father[y] = x;
}
};
struct BIPARTIT
{
vector<int> con[400005];
int parte[400005];
void add_edge(int x, int y)
{
con[x].push_back(y);
con[y].push_back(x);
}
void dfs(int nod)
{
for(int adj:con[nod])
{
if(parte[adj]==0)
{
parte[adj] = 3 - parte[nod];
dfs(adj);
}
}
}
bool solve()
{
for(int i=0;i<2*n;i++)
parte[i]=0;
for(int i=0;i<2*n;i++)
if(parte[i]==0)
dfs(i);
for(int i=0;i<2*n;i++)
for(int adj:con[i])
if(parte[i]==parte[adj])
return 0;
return 1;
}
};
int dx[4] = {-2,+2,0,0};
int dy[4] = {0,0,-2,+2};
int construct_roads(std::vector<int> x, std::vector<int> y)
{
n = x.size();
if (n == 1)
{
build({}, {}, {}, {});
return 1;
}
std::vector<int> solu, solv, sola, solb;
map<pair<int,int>,pair<int,bool>> mp;
for(int i=0;i<n;i++)
{
mp[{x[i],y[i]}] = {i,1};
}
DSU dsu;
dsu.init();
for(int i=0;i<n;i++)
{
for(int v=0;v<4;v++)
{
int newx = x[i]+dx[v], newy = y[i]+dy[v];
if(mp[{newx,newy}].second)
{
int j = mp[{newx,newy}].first;
if(dsu.get(i) != dsu.get(j))
{
dsu.unite(i,j);
solu.push_back(i);
solv.push_back(j);
}
}
}
}
if(dsu.siz[dsu.get(1)] != n)
return 0;
sola.resize(solu.size());
solb.resize(solu.size());
map<pair<int,int>,vector<int>> used;
for(int i=0;i<solu.size();i++)
{
int u = solu[i], v = solv[i];
pair<int,int> banca = {-1,-1};
if(x[u] == x[v])
{
int pas=0;
for(int newx:{x[u]-1, x[u]+1})
{
pair<int,int> cur = {newx, (y[u]+y[v])/2};
used[cur].push_back(2*i + pas);
pas++;
}
}
else
{
assert(y[u] == y[v]);
int pas=0;
for(int newy:{y[u]-1, y[u]+1})
{
pair<int,int> cur = {(x[u]+x[v])/2, newy};
used[cur].push_back(2*i + pas);
pas++;
}
}
}
BIPARTIT bipartit;
for(auto it:used)
{
if(it.second.size() >= 2)
{
for(int i=0;i<it.second.size();i++)
for(int j=i+1;j,it.second.size();j++)
bipartit.add_edge(it.second[i], it.second[j]);
}
}
if(!bipartit.solve())
return 0;
for(int i=0;i<solu.size();i++)
{
int u = solu[i], v = solv[i];
pair<int,int> banca = {-1,-1};
sola[i] = solb[i] = -1;
if(x[u] == x[v])
{
int pas=0;
for(int newx:{x[u]-1, x[u]+1})
{
pair<int,int> cur = {newx, (y[u]+y[v])/2};
if(bipartit.parte[2*i+pas] == 1)
{
sola[i] = cur.first;
solb[i] = cur.second;
}
pas++;
}
}
else
{
assert(y[u] == y[v]);
int pas=0;
for(int newy:{y[u]-1, y[u]+1})
{
pair<int,int> cur = {(x[u]+x[v])/2, newy};
if(bipartit.parte[2*i+pas] == 1)
{
sola[i] = cur.first;
solb[i] = cur.second;
}
pas++;
}
}
assert(sola[i]!=-1);
}
build(solu, solv, sola, solb);
return 1;
}
