#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 10;
struct query
{
int l, r, s, e;
query(int _l = 0, int _r = 0, int _s = 0, int _e = 0)
{
l = _l;
r = _r;
s = _s;
e = _e;
}
}ask[maxn];
int n, q, m, used0[maxn], used1[maxn];
vector < int > graph[maxn];
void bfs0(int v, int l)
{
if (v < l)
return;
used0[v] = 1;
queue < int > q;
q.push(v);
while(!q.empty())
{
int cur = q.front();
q.pop();
for (int u : graph[cur])
{
if (u < l)
continue;
if (used0[u] == 0)
{
q.push(u);
used0[u] = 1;
}
}
}
}
void bfs1(int v, int r)
{
if (v > r)
return;
used1[v] = 1;
queue < int > q;
q.push(v);
while(!q.empty())
{
int cur = q.front();
q.pop();
for (int u : graph[cur])
{
if (u > r)
continue;
if (used1[u] == 0)
{
q.push(u);
used1[u] = 1;
}
}
}
}
int solve_query(query cur)
{
for (int i = 0; i < n; i ++)
{
used0[i] = used1[i] = 0;
}
bfs0(cur.s, cur.l);
bfs1(cur.e, cur.r);
for (int i = 0; i < n; i ++)
{
if (used0[i] == 1 && used1[i] == 1)
return 1;
}
return 0;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R)
{
n = N;
q = L.size();
m = X.size();
for (int i = 0; i < q; i ++)
{
ask[i] = query(L[i], R[i], S[i], E[i]);
}
for (int i = 0; i < m; i ++)
{
graph[X[i]].push_back(Y[i]);
graph[Y[i]].push_back(X[i]);
}
vector < int > ans(q, 0);
for (int i = 0; i < q; i ++)
{
ans[i] = solve_query(ask[i]);
}
return ans;
}
