/*
Author of all code: Pedro BIGMAN Dias
Last edit: 15/02/2021
*/
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <deque>
#include <list>
#include <iomanip>
#include <stdlib.h>
#include <time.h>
#include <cstring>
#include "werewolf.h"
using namespace std;
typedef int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"Pedro Is The Master "<<i<<endl
#define INF 1000000000000000000LL
#define EPS ((ld)0.00000000001)
#define pi ((ld)3.141592653589793)
#define VV(vvvv,NNNN,xxxx); REP(iiiii,0,NNNN) {vvvv.pb(xxxx);}
ll mod=1000000007LL;
template<class A=ll>
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}
template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}}
class Graph
{
public:
ll N;
vector<vector<ll> > adj;
vector<bool> visited; //for DFS/BFS
Graph() {ll N=0LL;}
Graph(vector<vector<ll> > ad)
{
adj=ad; N=adj.size(); REP(i,0,N) {visited.pb(false);}
}
void Reset()
{
REP(i,0,N) {visited[i]=false;}
}
void DFS(ll s, ll L, bool smaller)
{
if(visited[s]) {return;}
visited[s]=true;
REP(i,0,adj[s].size())
{
if((smaller && adj[s][i]>L)||(!smaller && adj[s][i]<L)) {continue;}
if(!visited[adj[s][i]]) {DFS(adj[s][i],L,smaller);}
}
return;
}
};
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R)
{
ll M = X.size();
vector<vector<ll> > adj; VV(adj,N,{});
REP(i,0,M) {adj[X[i]].pb(Y[i]); adj[Y[i]].pb(X[i]);}
Graph G(adj);
ll Q = S.size();
vector<ll> ans;
REP(i,0,Q)
{
vector<bool> visited1,visited2;
G.Reset(); G.DFS(S[i],L[i],false); visited1=G.visited;
G.Reset(); G.DFS(E[i],R[i],true); visited2=G.visited;
ll ok=0;
REP(j,0,N) {if(visited1[j]&&visited2[j]) {ok=1;}}
ans.pb(ok);
}
return ans;
}
