#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> tree[800001];
void add(int no,int l,int r,int aa,int bb,int i){
if(r<aa or l>bb){
return;
}
if(aa<=l and r<=bb){
tree[no].pb(i);
}
else{
int mid=(l+r)/2;
add(no*2+1,l,mid,aa,bb,i);
add(no*2+2,mid+1,r,aa,bb,i);
}
}
int ans2[200001];
void update(int no,int l,int r,int i){
for(auto j:tree[no]){
if(vis[j]==0){
ans2[j]=1;
}
}
tree[no].clear();
if(l<r){
int mid=(l+r)/2;
if(i<=mid){
update(no*2+1,l,mid,i);
}
else{
update(no*2+2,mid+1,r,i);
}
}
}
//vector<int> pre5[200001];
vector<pair<pair<int,int>,int>> pre5[200001];
vector<int> pre6[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++){
pre5[ran[i].a].pb({ran2[i],i});
pre6[ran[i].b].pb(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[stt2[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;
}*/
}
for(int i=0;i<n;i++){
for(auto j:pre5[i]){
add(0,0,n-1,j.a.a,j.a.b,j.b);
}
update(0,0,n-1,st2[stt[i]]);
for(auto j:pre6[i]){
vis[j]=1;
}
}
for(int i=0;i<q;i++){
ans.pb(ans2[i]);
}
return ans;
}
