//#include "grader.cpp"
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
namespace{
const int mxn=2e5+5;
vector<int> adj[mxn];
set<pair<int,int>> S[mxn];
vector<pair<int,int>> R[mxn];
}
struct DSU{
vector<int> e;
vector<vector<int>> B;
DSU(int n){
e=vector<int>(n,-1);
B.resize(n);
for(int i=0;i<n;i++){
B[i].push_back(i);
R[i].push_back({-1,i});
S[i].insert({i,-1});
}
}
int find(int x){
return (e[x]<0?x:e[x]=find(e[x]));
}
bool unite(int a,int b,int t){
a=find(a);
b=find(b);
if(a==b) return false;
if(e[a]>e[b]) swap(a,b);
e[a]+=e[b];
e[b]=a;
for(auto v:B[b]){
S[v].insert({a,t});
R[v].push_back({t,a});
B[a].push_back(v);
}
vector<int>().swap(B[b]);
return true;
}
};
struct DSU2{
vector<int> e;
DSU2(int n){
e=vector<int>(n,-1);
}
int find(int x){
return (e[x]<0?x:e[x]=find(e[x]));
}
bool unite(int a,int b){
a=find(a);
b=find(b);
if(a==b) return false;
if(e[a]>e[b]) swap(a,b);
e[a]+=e[b];
e[b]=a;
for(auto v:S[b]){
S[a].insert(v);
}
set<pair<int,int>>().swap(S[b]);
return true;
}
bool query(int a,int b,int tl,int tr){
a=find(a);
int sz=(int)R[b].size();
for(int i=0;i<sz-1;i++){
int l=R[b][i].f;
int r=R[b][i+1].f;
int v=R[b][i].s;
if(l>tr) break;
r=min(r,tr+1);
auto L=S[a].lower_bound({v,l});
auto R=S[a].lower_bound({v,r});
if(L!=R) return true;
}
return false;
}
};
std::vector<int> check_validity(int n, std::vector<int> X, std::vector<int> Y,std::vector<int> S, std::vector<int> E,std::vector<int> L, std::vector<int> RR) {
int m=(int)X.size();
for(int i=0;i<m;i++){
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
DSU dsu(n);
for(int i=0;i<n;i++){
for(auto v:adj[i]){
if(v<i){
dsu.unite(i,v,i);
}
}
}
int q=(int)L.size();
vector<vector<int>> qs(n);
vector<int> ans(q);
for(int i=0;i<q;i++){
qs[L[i]].push_back(i);
}
for(int i=0;i<n;i++){
R[i].push_back(make_pair(n,dsu.find(i)));
}
DSU2 dsu2(n);
for(int i=n-1;i>=0;i--){
for(auto v:adj[i]){
if(v>i){
dsu2.unite(i,v);
}
}
for(auto v:qs[i]){
ans[v]=dsu2.query(S[v],E[v],i,RR[v]);
}
}
return ans;
}
/*
6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/
