#include "parks.h"
#include <bits/stdc++.h>
#define rep(a,b,c) for(int a=int(b); a<int(c); ++a)
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#pragma once
bool dfs(int a, int L, vector<vi>& g, vi& btoa, vi& A, vi& B) {
if (A[a] != L) return 0;
A[a] = -1;
for (int b : g[a]) if (B[b] == L + 1) {
B[b] = 0;
if (btoa[b] == -1 || dfs(btoa[b], L + 1, g, btoa, A, B))
return btoa[b] = a, 1;
}
return 0;
}
int hopcroftKarp(vector<vi>& g, vi& btoa) {
int res = 0;
vi A(g.size()), B(btoa.size()), cur, next;
for (;;) {
fill(all(A), 0);
fill(all(B), 0);
/// Find the starting nodes for BFS (i.e. layer 0).
cur.clear();
for (int a : btoa) if(a != -1) A[a] = -1;
rep(a,0,sz(g)) if(A[a] == 0) cur.push_back(a);
/// Find all layers using bfs.
for (int lay = 1;; lay++) {
bool islast = 0;
next.clear();
for (int a : cur) for (int b : g[a]) {
if (btoa[b] == -1) {
B[b] = lay;
islast = 1;
}
else if (btoa[b] != a && !B[b]) {
B[b] = lay;
next.push_back(btoa[b]);
}
}
if (islast) break;
if (next.empty()) return res;
for (int a : next) A[a] = lay;
cur.swap(next);
}
/// Use DFS to scan for augmenting paths.
rep(a,0,sz(g))
res += dfs(a, 0, g, btoa, A, B);
}
}
/*int faster_matching(vector<vi>& g, vi& btoa) {
vector<vi> g2(btoa.size());
rep(i,0,g.size()) {
rep(j,0,g[i].size()) {
g2[g[i][j]].push_back(i);
}
}
vector<int> deg_one;
rep(i,0,g.size()) {
if(g[i].size()==1) {
deg_one.push_back(i);
}
}
int current = 0;
while(true)
rep(i,0,deg_one.size()) {
current = i;
}
}*/
vector<int> parent;
vector<int> s;
int find(int x) {
if(x==parent[x]) return x;
else return parent[x]=find(parent[x]);
}
void makeset(int x) {
parent[x]=x;
}
bool sameset(int x, int y) {
return find(x)==find(y);
}
void join(int x, int y) {
int xroot = find(x);
int yroot = find(y);
if(s[xroot]>s[yroot]) {
parent[yroot]=xroot;
s[xroot] += s[yroot];
} else {
parent[xroot]=yroot;
s[yroot] += s[xroot];
}
}
int construct_roads(vector<int> x, vector<int> y) {
if (x.size() == 1) {
build({}, {}, {}, {});
return 1;
}
int n = x.size();
int M = 2*1e5+1;
vector<vector<pair<int,int>>> x_fountains(M);
vector<vector<pair<int,int>>> y_fountains(M);
// first is the coordinate
// second is the index.
rep(i,0,n) {
x_fountains[x[i]].emplace_back(y[i],i);
y_fountains[y[i]].emplace_back(x[i],i);
}
rep(i,0,M) {
sort(x_fountains[i].begin(), x_fountains[i].end());
sort(y_fountains[i].begin(), y_fountains[i].end());
}
vector<int> u, v, a, b;
parent.clear();
parent.resize(n);
s.resize(n);
rep(i,0,n) makeset(i);
rep(i,0,M) {
rep(j,1,x_fountains[i].size()) {
int ind1 = x_fountains[i][j-1].second;
int y1 = x_fountains[i][j-1].first;
int ind2 = x_fountains[i][j].second;
int y2 = x_fountains[i][j].first;
if(y2-y1!=2) continue;
if(sameset(ind1,ind2)) continue;
join(ind1,ind2);
u.push_back(ind1);
v.push_back(ind2);
}
}
rep(i,0,M) {
rep(j,1,y_fountains[i].size()) {
int ind1 = y_fountains[i][j-1].second;
int x1 = y_fountains[i][j-1].first;
int ind2 = y_fountains[i][j].second;
int x2 = y_fountains[i][j].first;
if(x2-x1!=2) continue;
if(sameset(ind1,ind2)) continue;
join(ind1,ind2);
u.push_back(ind1);
v.push_back(ind2);
}
}
int num_roads = u.size();
if(num_roads!=n-1) return 0;
map<pair<int,int>, int> potential_benches;
vector<pair<int,int>> potential_benches2;
vector<vector<int>> graph(num_roads);
rep(i,0,num_roads) {
int f1 = u[i];
int f2 = v[i];
vector<pair<int,int>> temp;
if(x[f1]==x[f2]) {
int mid = (y[f1]+y[f2])/2;
temp.emplace_back(x[f1]-1, mid);
temp.emplace_back(x[f1]+1, mid);
} else {
assert(y[f1]==y[f2]);
int mid = (x[f1]+x[f2])/2;
temp.emplace_back(mid, y[f1]-1);
temp.emplace_back(mid, y[f1]+1);
}
rep(j,0,temp.size()) {
if (!potential_benches.count(temp[j])) {
potential_benches[temp[j]]=potential_benches.size();
potential_benches2.emplace_back(temp[j]);
}
graph[i].push_back(potential_benches[temp[j]]);
}
}
vector<int> btoa(potential_benches.size(),-1);
if(hopcroftKarp(graph, btoa)!=num_roads) return 0;
a.resize(num_roads);
b.resize(num_roads);
rep(i,0,potential_benches2.size()) {
if(btoa[i] != -1) {
a[btoa[i]] = potential_benches2[i].first;
b[btoa[i]] = potential_benches2[i].second;
}
}
build(u, v, a, b);
return 1;
}
