#include "parks.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
#include <random>
#include <chrono>
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
const int INF = 202020;
vector<pii> lsX[INF];
vector<pii> lsY[INF];
vector<pii> eg, tr;
int par[202020];
int fnd(int x) { return x == par[x] ? x : par[x] = fnd(par[x]); }
void uni(int x, int y) { par[fnd(x)] = fnd(y); }
vector<int> U, V, A, B;
vector<int> gph[404040];
int ord[404040];
int scc[404040];
int scnt = 0, cnt = 0;
vector<int> S;
int dfs(int x, int p)
{
int ret = ord[x] = ++cnt;
S.push_back(x);
for(int y : gph[x]) if(y != p)
{
if(!ord[y]) ret = min(ret, dfs(y, x));
else if(!scc[y]) ret = min(ret, ord[y]);
}
if(ret >= ord[x])
{
++scnt;
while(S.back() != x) scc[S.back()] = scnt, S.pop_back();
scc[S.back()] = scnt, S.pop_back();
}
return ret;
}
int construct_roads(vector<int> x, vector<int> y)
{
int n = x.size();
for(int i = 0; i < n; ++i) lsX[x[i]].push_back({y[i], i});
for(int i = 0; i < n; ++i) lsY[y[i]].push_back({x[i], i});
for(int i = 0; i < INF; ++i)
{
sort(lsX[i].begin(), lsX[i].end());
for(int j = 0; j < (int)lsX[i].size() - 1; ++j)
if(lsX[i][j + 1].ff - lsX[i][j].ff == 2) eg.push_back({lsX[i][j].ss, lsX[i][j + 1].ss});
}
for(int i = 0; i < INF; ++i)
{
sort(lsY[i].begin(), lsY[i].end());
for(int j = 0; j < (int)lsY[i].size() - 1; ++j)
if(lsY[i][j + 1].ff - lsY[i][j].ff == 2) eg.push_back({lsY[i][j].ss, lsY[i][j + 1].ss});
}
unsigned seed = chrono::steady_clock::now().time_since_epoch().count();
mt19937 rng(seed);
for(int cs = 0; cs < 30; ++cs)
{
shuffle(eg.begin(), eg.end(), rng);
for(int i = 0; i < 202020; ++i) par[i] = i;
tr.clear();
for(auto i : eg) if(fnd(i.ff) != fnd(i.ss)) tr.push_back(i), uni(i.ff, i.ss);
if(tr.size() != n - 1) return 0;
pii C[n - 1], D[n - 1];
vector<pii> pr;
int c = 0;
for(auto [i, j] : tr)
{
if(x[i] == x[j])
{
C[c] = {x[i] - 1, y[i] + 1};
D[c] = {x[i] + 1, y[i] + 1};
}
else
{
C[c] = {x[i] + 1, y[i] - 1};
D[c] = {x[i] + 1, y[i] + 1};
}
pr.push_back(C[c]);
pr.push_back(D[c]);
++c;
}
sort(pr.begin(), pr.end());
pr.resize(unique(pr.begin(), pr.end()) - pr.begin());
int E[n - 1], F[n - 1];
for(int i = 0; i < n - 1; ++i) E[i] = lower_bound(pr.begin(), pr.end(), C[i]) - pr.begin();
for(int i = 0; i < n - 1; ++i) F[i] = lower_bound(pr.begin(), pr.end(), D[i]) - pr.begin();
int N = pr.size();
vector<pii> ls[N];
for(int i = 0; i < n - 1; ++i) ls[E[i]].push_back({i, 0});
for(int i = 0; i < n - 1; ++i) ls[F[i]].push_back({i, 1});
cnt = scnt = 0;
for(int i = 0; i < 2 * n; ++i) gph[i].clear(), ord[i] = scc[i] = 0;
S.clear();
for(int i = 0; i < N; ++i)
{
int sz = ls[i].size();
for(int j = 0; j < sz; ++j)
{
for(int k = 0; k < sz; ++k)
{
if(j != k)
{
int p = ls[i][j].ff + ls[i][j].ss * n;
int q = ls[i][k].ff + (!ls[i][k].ss) * n;
gph[p].push_back(q);
}
}
}
}
for(int i = 0; i < 2 * n; ++i) if(!ord[i]) dfs(i, -1);
bool flag = true;
for(int i = 0; i < n - 1; ++i) if(scc[i] == scc[i + n]) flag = false;
if(!flag) continue;
for(int i = 0; i < n - 1; ++i)
{
U.push_back(tr[i].ff);
V.push_back(tr[i].ss);
if(scc[i] < scc[i + n])
{
A.push_back(C[i].ff);
B.push_back(C[i].ss);
}
else
{
A.push_back(D[i].ff);
B.push_back(D[i].ss);
}
}
build(U, V, A, B);
return 1;
}
return 0;
}
