#include "parks.h"
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("-Ofast")
#include <bits/stdc++.h>
using namespace std;
typedef int in;
// #define int long long
#define double long double
#define f first
#define s second
#define pb push_back
#define pp push
#define ceil(x,y) (x/y)+(x%y!=0)*(x*y<0?0:1)
#define floor(x,y) (x/y)+(x%y!=0)*(x*y<0?-1:0)
const int MAAX=1e18;
const int MOD=1e9+7;
const int MAX=1e9;
bool vis[200010],lst[200010],ch[200010];
map<pair<int,int>,int> mp;
map<pair<int,int>,int> tk;
in construct_roads(vector<in> x, vector<in> y) {
    if (x.size() == 1) {
		build({}, {}, {}, {});
        return 1;
    }
    vector<in> ansu,ansv,ansa,ansb;
    int n=x.size();
    for(int i=0;i<n;i++){
    	mp[{x[i],y[i]}]=i+1;
    	ch[i]=1;
    }
   	int cur=1;
   	queue<int> q;
   	srand(time(0));
   	int rn=rand()%n;
   	q.pp(rn);
   	vis[rn]=1;
   	while(q.size()&&cur<n){
   		int curx=x[q.front()],cury=y[q.front()],curid=q.front();
   		q.pop();
   		if(mp[{curx-2,cury}]&&!vis[mp[{curx-2,cury}]-1]){
   			int idx=mp[{curx-2,cury}]-1;
   			vis[idx]=1;
   			cur++;
   			q.pp(idx);
   			ansu.pb(curid);
   			ansv.pb(idx);
   		}
   		if(mp[{curx+2,cury}]&&!vis[mp[{curx+2,cury}]-1]){
   			int idx=mp[{curx+2,cury}]-1;
   			vis[idx]=1;
   			cur++;
   			q.pp(idx);
   			ansu.pb(curid);
   			ansv.pb(idx);
   		}
   		if(mp[{curx,cury-2}]&&!vis[mp[{curx,cury-2}]-1]){
   			int idx=mp[{curx,cury-2}]-1;
   			vis[idx]=1;
   			cur++;
   			q.pp(idx);
   			ansu.pb(curid);
   			ansv.pb(idx);
   		}
   		if(mp[{curx,cury+2}]&&!vis[mp[{curx,cury+2}]-1]){
   			int idx=mp[{curx,cury+2}]-1;
   			vis[idx]=1;
   			cur++;
   			q.pp(idx);
   			ansu.pb(curid);
   			ansv.pb(idx);
   		}
   	}
   	if(cur<n)
	    return 0;
	int c=0;
	int t=time(0);
	while(1){
		bool cor=1;
		for(int i=0;i<ansu.size();i++){
			if(time(0)-t==3){
				return 0;
			}
			int x1=x[ansu[i]],y1=y[ansu[i]],x2=x[ansv[i]],y2=y[ansv[i]];
			if(x1==x2+2){
				int rnd=lst[i];
				if(ch[i])
					rnd=rand()%2;
				ch[i]=0;
				lst[i]=rnd;
				int bx=x1-1,by=y1-1+2*rnd;
				if(tk[{bx,by}])
					rnd=!rnd;
				by=y1-1+2*rnd;
				if(tk[{bx,by}]){
					ch[i]=1;
					ch[tk[{bx,by}]-1]=1;
					rnd=!rnd;
					by=y1-1+2*rnd;
					ch[tk[{bx,by}]-1]=1;
					cor=0;
					continue;
				}
				tk[{bx,by}]=i+1;
				ansa.pb(bx);
				ansb.pb(by);
			}
			else if(x1==x2-2){
				int rnd=lst[i];
				if(ch[i])
					rnd=rand()%2;
				ch[i]=0;
				lst[i]=rnd;
				int bx=x1+1,by=y1-1+2*rnd;
				if(tk[{bx,by}])
					rnd=!rnd;
				by=y1-1+2*rnd;
				if(tk[{bx,by}]){
					ch[i]=1;
					ch[tk[{bx,by}]-1]=1;
					rnd=!rnd;
					by=y1-1+2*rnd;
					ch[tk[{bx,by}]-1]=1;
					cor=0;
					continue;
				}
				tk[{bx,by}]=i+1;
				ansa.pb(bx);
				ansb.pb(by);
			}
			else if(y1==y2+2){
				int rnd=lst[i];
				if(ch[i])
					rnd=rand()%2;
				ch[i]=0;
				lst[i]=rnd;
				int bx=x1-1+2*rnd,by=y1-1;
				if(tk[{bx,by}])
					rnd=!rnd;
				bx=x1-1+2*rnd;
				if(tk[{bx,by}]){
					ch[i]=1;
					ch[tk[{bx,by}]-1]=1;
					rnd=!rnd;
					bx=x1-1+2*rnd;
					ch[tk[{bx,by}]-1]=1;
					cor=0;
					continue;
				}
				tk[{bx,by}]=i+1;
				ansa.pb(bx);
				ansb.pb(by);
			}
			else{
				int rnd=lst[i];
				if(ch[i])
					rnd=rand()%2;
				ch[i]=0;
				lst[i]=rnd;
				int bx=x1-1+2*rnd,by=y1+1;
				if(tk[{bx,by}])
					rnd=!rnd;
				bx=x1-1+2*rnd;
				if(tk[{bx,by}]){
					ch[i]=1;
					ch[tk[{bx,by}]-1]=1;
					rnd=!rnd;
					bx=x1-1+2*rnd;
					ch[tk[{bx,by}]-1]=1;
					cor=0;
					continue;
				}
				tk[{bx,by}]=i+1;
				ansa.pb(bx);
				ansb.pb(by);
			}
		}
		if(cor)
			break;
		tk.clear();
		ansa.clear();
		ansb.clear();
		if(time(0)-t==3){
			return 0;
		}
	}
	build(ansu,ansv,ansa,ansb);
	return 1;
}