#include <bits/stdc++.h>
#include "werewolf.h"
#define F first
#define S second
#define pb push_back
using namespace std;
struct DSU {
vector<int>par;
void init(int n) {
par.resize(n + 10);
for(int i = 0; i < n; i++) par[i] = i;
}
int get(int x) {
return (x == par[x] ? x : par[x] = get(par[x]));
}
void unite(int u,int v) {
u = get(u); v = get(v);
if(u != v) par[u] = v;
}
bool same(int u,int v) {
return (get(u) == get(v));
}
};
bool cmpL(pair<int,int>a,pair<int,int>b) {
return min(a.F,a.S) > min(b.F,b.S);
}
bool cmpR(pair<int,int>a,pair<int,int>b) {
return max(a.F,a.S) < max(b.F,b.S);
}
vector<int> check_validity(int N,vector<int> X,vector<int> Y,vector<int> S,vector<int> E,vector<int> L,vector<int> R) {
vector<pair<int,int>>edges;
int m = X.size(),q = S.size(),n = N;
for(int i = 0; i < m; i++) {
edges.pb({X[i],Y[i]});
}
vector<int>ans(q);
for(int j = 0; j < q; j++) {
int s = S[j],e = E[j],l = L[j],r = R[j];
DSU dsu[2];
dsu[0].init(n);
dsu[1].init(n);
sort(edges.begin(),edges.end(),cmpL);
for(int i = 0; i < m; i++) {
if(min(edges[i].F,edges[i].S) < l) break;
dsu[0].unite(edges[i].F,edges[i].S);
}
sort(edges.begin(),edges.end(),cmpR);
for(int i = 0; i < m; i++) {
if(max(edges[i].F,edges[i].S) > r) break;
dsu[1].unite(edges[i].F,edges[i].S);
}
for(int i = 0; i < n; i++) {
if(dsu[0].same(i,e) && dsu[1].same(i,s)) ans[j] = 1;
if(dsu[1].same(i,e) && dsu[0].same(i,s)) ans[j] = 1;
}
}
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
*/
