#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
const int mxn=2e6+5;
int n,m,q,tmm,nxt=1,mn[mxn],mx[mxn],p[mxn],sz[mxn],idx[mxn],idx2[mxn],l[mxn],r[mxn],l2[mxn],r2[mxn],L[mxn*20],R[mxn*20],room[mxn],tree[mxn*20],par[mxn][20],par2[mxn][20];
vector<int>vt[mxn];
vector<int>vtx[mxn],vty[mxn];
void build(int node,int l,int r){
if(l==r) return;
L[node]=++nxt;
R[node]=++nxt;
int m=(l+r)/2;
build(L[node],l,m);
build(R[node],m+1,r);
}
int update(int node,int l,int r,int pos){
int nw=++nxt;
if(l==r){
tree[nw]=1;
return nw;
}
int m=(l+r)/2;
L[nw]=L[node],R[nw]=R[node];
if(pos<=m){
L[nw]=update(L[nw],l,m,pos);
}
else{
R[nw]=update(R[nw],m+1,r,pos);
}
tree[nw]=tree[L[nw]]+tree[R[nw]];
return nw;
}
int query(int node,int node2,int l,int r,int ql,int qr){
if(l>qr||r<ql){
return 0;
}
if(ql<=l&&r<=qr){
return tree[node]-tree[node2];
}
int m=(l+r)/2;
return query(L[node],L[node2],l,m,ql,qr)+query(R[node],R[node2],m+1,r,ql,qr);
}
void dfs(int u,int p){
par[u][0]=p;
l[u]=++tmm;
idx[tmm]=u;
for(int v:vtx[u]){
if(v!=p){
dfs(v,u);
}
}
r[u]=tmm;
}
void dfs2(int u,int p){
par2[u][0]=p;
l2[u]=++tmm;
idx2[tmm]=u;
for(int v:vty[u]){
if(v!=p){
dfs2(v,u);
}
}
r2[u]=tmm;
}
int fnd(int u){
if(p[u]==u) return u;
return p[u]=fnd(p[u]);
}
void Union(int u,int v){
u=fnd(u);
v=fnd(v);
if(u!=v){
if(sz[v]>sz[u]) swap(u,v);
sz[u]+=sz[v];
p[v]=u;
mn[u]=min(mn[u],mn[v]);
mx[u]=max(mx[u],mx[v]);
}
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> lx,vector<int> rx) {
q = S.size();
n=N;
m=X.size();
for(int i=0;i<m;i++){
int u=X[i]+1,v=Y[i]+1;
vt[u].pb(v);
vt[v].pb(u);
}
for(int i=1;i<=n;i++){
p[i]=i;
sz[i]=1;
mx[i]=i;
mn[i]=i;
}
for(int i=n;i>=1;i--){
int u=i;
for(int v:vt[u]){
if(v>u&&fnd(u)!=fnd(v)){
int nw=mn[fnd(v)];
vtx[u].pb(nw);
vtx[nw].pb(u);
Union(u,nw);
}
}
}
for(int i=1;i<=n;i++){
p[i]=i;
sz[i]=1;
mx[i]=i;
mn[i]=i;
}
for(int i=1;i<=n;i++){
int u=i;
for(int v:vt[u]){
if(v<u&&fnd(v)!=fnd(u)){
int nw=mx[fnd(v)];
vty[u].pb(nw);
vty[nw].pb(u);
Union(u,nw);
}
}
}
tmm=0;
dfs(1,-1);
par[1][0]=1;
tmm=0;
dfs2(n,-1);
par2[n][0]=n;
for(int j=1;j<20;j++){
for(int i=1;i<=n;i++){
par[i][j]=par[par[i][j-1]][j-1];
par2[i][j]=par2[par2[i][j-1]][j-1];
}
}
build(1,1,n);
room[0]=1;
for(int i=1;i<=n;i++){
int a=idx2[i];
int pos=l[a];
room[i]=update(room[i-1],1,n,pos);
}
vector<int>ans;
for(int i=0;i<q;i++){
int u=S[i]+1,v=E[i]+1,a=lx[i],b=rx[i];
for(int j=19;j>=0;j--){
if(par[u][j]-1>=a){
u=par[u][j];
}
if(par2[v][j]-1<=b){
v=par2[v][j];
}
}
if(query(room[r2[v]],room[l2[v]-1],1,n,l[u],r[u])>0){
ans.pb(1);
}
else{
ans.pb(0);
}
}
return ans;
}
