#include <bits/stdc++.h>
using namespace std;
#define a first
#define b second
#define pb push_back
typedef long long llo;
#include "werewolf.h"
vector<pair<int,int>> pre[200001];
vector<pair<int,int>> pre2[200001];
vector<pair<int,int>> pre3[200001];
vector<pair<int,int>> pre4[200001];
int par[200001];
int ss[200001];
vector<int> adj[200001];
vector<int> adj2[200001];
int find(int no){
if(par[no]==no){
return no;
}
par[no]=find(par[no]);
return par[no];
}
int co=-1;
int st[200001];
int stt[200001];
void dfs(int no){
co++;
st[no]=co;
stt[co]=no;
for(auto j:adj[no]){
dfs(j);
}
}
int co2=-1;
int st2[200001];
int stt2[200001];
void dfs2(int no){
co2++;
st2[no]=co2;
stt2[co2]=no;
for(auto j:adj2[no]){
dfs2(j);
}
}
pair<int,int> ran[200001];
pair<int,int> ran2[200001];
int vis[200001];
vector<int> check_validity(int n,vector<int> xx,vector<int> yy,
vector<int> ss3,vector<int> ee,
vector<int> l,vector<int> r) {
int m=xx.size();
for(int i=0;i<m;i++){
pre[min(xx[i],yy[i])].pb({xx[i],yy[i]});
pre2[max(xx[i],yy[i])].pb({xx[i],yy[i]});
}
for(int i=0;i<n;i++){
par[i]=i;
ss[i]=1;
}
int q=ss3.size();
for(int i=0;i<q;i++){
pre3[l[i]].pb({ss3[i],i});
pre4[r[i]].pb({ee[i],i});
}
vector<pair<pair<int,int>,int>> qq;
for(int i=n-1;i>=0;i--){
for(auto j:pre[i]){
int x=find(j.a);
int y=find(j.b);
if(x!=y){
// cout<<x<<":"<<y<<endl;
adj[x].pb(y);
par[y]=x;
ss[x]+=ss[y];
}
}
for(auto j:pre3[i]){
qq.pb({{find(j.a),ss[find(j.a)]},j.b});
// cout<<j.a<<"."<<find(j.a)<<"/"<<ss[find(j.a)]<<"/"<<j.b<<endl;
}
}
dfs(find(0));
for(auto j:qq){
ran[j.b]={st[j.a.a],st[j.a.a]+j.a.b-1};
}
/*for(int i=0;i<q;i++){
cout<<ran[i].a<<":"<<ran[i].b<<endl;
for(int j=ran[i].a;j<=ran[i].b;j++){
cout<<stt[j]<<",";
}
cout<<endl;
}*/
for(int i=0;i<n;i++){
par[i]=i;
ss[i]=1;
}
vector<pair<pair<int,int>,int>> qq2;
for(int i=0;i<n;i++){
for(auto j:pre2[i]){
int x=find(j.a);
int y=find(j.b);
if(x!=y){
adj2[x].pb(y);
//cout<<x<<":"<<y<<endl;
par[y]=x;
ss[x]+=ss[y];
}
}
for(auto j:pre4[i]){
qq2.pb({{find(j.a),ss[find(j.a)]},j.b});
}
}
dfs2(find(0));
for(auto j:qq2){
ran2[j.b]={st2[j.a.a],st2[j.a.a]+j.a.b-1};
}
vector<int> ans;
for(int i=0;i<q;i++){
for(int j=ran[i].a;j<=ran[i].b;j++){
vis[stt[j]]+=1;
}
int kk=0;
for(int j=ran2[i].a;j<=ran2[i].b;j++){
vis[stt2[j]]+=1;
if(vis[stt[j]]==2){
kk=1;
}
}
ans.pb(kk);
for(int j=ran[i].a;j<=ran[i].b;j++){
vis[stt[j]]-=1;
}
for(int j=ran2[i].a;j<=ran2[i].b;j++){
vis[stt2[j]]-=1;
}
}
return ans;
}
