#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define fi first
#define se second
#define FOR(i,a) for(int i=0;i<(a);i++)
#define FORE(i,a,b) for(int i=(a);i<(b);i++)
#define sp <<' '<<
#define mid (l+r)/2
#define all(x) x.begin(),x.end()
#define carp(a,b) ((a%MOD)*(b%MOD))%MOD
#define topla(a,b) ((a%MOD)+(b%MOD))%MOD
#define pb push_back
#define DEBUG(x) cout<<#x sp x<<endl;
#define cont(x) for(auto el:x) cout<<el<<' ';cout<<endl;
#define contp(x) for(auto el:x) cout<<el.fi<<'-'<<el.se<<' ';cout<<endl;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
const int MAXN=2e5+6;
const int INF=1e9+7;
#include "werewolf.h"
int n,q;
int curl,curr;
bool f;
bool vis[MAXN],vis2[MAXN];
vi adj[MAXN];
void dfs(int nd){
if (f) vis[nd]=true;
else vis2[nd]=true;
for(auto kom:adj[nd]){
if(f and vis[kom]) continue;
if(!f and vis2[kom]) continue;
if(f and nd>=curl) dfs(kom);
if(!f and nd<=curr) dfs(kom);
}
}
vi check_validity(int N, vi x, vi y, vi S, vi E, vi L, vi R){
//line
n=N;
FOR(i,x.size()){
x[i]++;y[i]++;
adj[x[i]].pb(y[i]);
adj[y[i]].pb(x[i]);
}
q=S.size();
vi ans;
FOR(i,q){
int bas=S[i]+1;
int son=E[i]+1;
curl=L[i]+1;
curr=R[i]+1;
f=true;
dfs(bas);
f=false;
dfs(son);
bool pos=false;
FORE(i,1,n+1){
if(vis[bas] and vis2[son] and vis[i] and vis2[i]){
pos=true;
}
vis[i]=vis2[i]=false;
}
if(pos) ans.pb(1);
else ans.pb(0);
}
return ans;
/*int Q = S.size();
vi A(Q);
for (int i = 0; i < Q; ++i) {
A[i] = 0;
}
return A;*/
}
