#include "werewolf.h"
#include<bits/stdc++.h>
#define fi first
#define se second
//#define int long long
using namespace std;
using ll = long long;
using ii = pair<int, int>;
using aa = array<int,3>;
const int N = 2e5+5;
const int INF = 1e9;
const int MOD = 1e9+7;
struct KRTTT {
int p[N];
int n;
int w[N];
vector<int> adj[N];
int get(int u) {
if(p[u]==u) return u;
return p[u]=get(p[u]);
}
void unite(int u,int v,int wei) {
u=get(u);
v=get(v);
if(u==v) return;
n++;
p[u]=p[v]=p[n]=n;
w[n]=wei;
adj[n].push_back(u);
adj[n].push_back(v);
return;
}
int timer=0;
int up[N][18];
int eu[N],out[N];
int rev[N];
void dfs(int u) {
eu[u]=++timer;
rev[timer]=u;
for(int i=1;i<18;i++) {
up[u][i]=up[up[u][i-1]][i-1];
}
for(int v:adj[u]) {
up[v][0]=u;
dfs(v);
}
out[u]=timer;
}
bool inside(int u,int v) {
return (u==0) || (eu[u]<=eu[v] && out[v]<=out[u]);
}
int lca(int u,int v) {
//cout << up[u][0] << ' ' << v << endl;
for(int i=17;i>=0;i--) {
if(!inside(up[u][i],v)) {
u=up[u][i];
}
}
return w[up[u][0]];
}
int getu(int u) {
return rev[u];
}
} KRT;
struct DSUUU {
vector<int> c[N];
set<int> s[N];
int p[N];
void unite(int u,int v) {
u=p[u];
v=p[v];
if(u==v) return;
if(c[u].size()<c[v].size()) swap(u,v);
for(int x:c[v]) {
c[u].push_back(x);
p[x]=u;
}
for(int x:s[v]) {
s[u].insert(x);
}
s[v].clear();
c[v].clear();
}
bool solve(int l,int r,int st,int t) {
st=p[st];
//cout << KRT.w[7] << endl;
//for(int x:s[st]) cout << x << ' ';
//cout << endl;
auto it=s[st].lower_bound(KRT.eu[t]);
if(it!=s[st].end()) {
//cout << t << ' ';
if(KRT.lca(KRT.getu(*it),t)<=r)return 1;
}
if(it!=s[st].begin()) {
--it;
if(KRT.lca(KRT.getu(*it),t)<=r)return 1;
}
return 0;
}
} DSU;
int L[N];
int R[N];
int S[N];
int E[N];
bool cmp(int x,int y) {
return L[x]>L[y];
}
int qr[N];
aa edge[N];
aa edge1[N];
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> ST, vector<int> ED, vector<int> LE, vector<int> RI) {
int n=N,m=X.size(),q=ST.size();
for(int i=1;i<=m;i++) {
int u=X[i-1],v=Y[i-1];
edge[i]={max(u,v),u,v};
edge1[i]={min(u,v),u,v};
}
sort(edge+1,edge+1+m);
for(int i=0;i<n;i++) {
KRT.p[i]=i;
}
KRT.n=n-1;
for(int i=1;i<=m;i++) {
KRT.unite(edge[i][1],edge[i][2],edge[i][0]);
}
KRT.dfs(KRT.n);
//cout << 1;
for(int i=1;i<=q;i++) {
L[i]=LE[i-1];
R[i]=RI[i-1];
S[i]=ST[i-1];
E[i]=ED[i-1];
qr[i]=i;
//cout << S[i] << endl;
}
for(int i=0;i<n;i++) {
DSU.p[i]=i;
DSU.c[i].push_back(i);
DSU.s[i].insert(KRT.eu[i]);
}
sort(qr+1,qr+q+1,cmp);
int j=m;
sort(edge1+1,edge1+1+m);
vector<int> ans(q,0);
//for(int x:ans) cout << x << endl;
for(int i=1;i<=q;i++) {
while(j>0 && edge1[j][0]>=L[qr[i]]) {
DSU.unite(edge1[j][1],edge1[j][2]);
//cout << edge1[j][1] << ' ' << edge1[j][2] << endl;
j--;
}
//cout << endl;
ans[qr[i]-1]=DSU.solve(L[qr[i]],R[qr[i]],S[qr[i]],E[qr[i]]);
//cout << endl;
}
return ans;
}
