#include <iostream>
#include <algorithm>
#include <cstring>
#include <iomanip>
#include <fstream>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <stack>
#include <queue>
#include <assert.h>
#include <limits>
#include <cstdio>
#include <complex>
#include "werewolf.h"
using namespace std;
typedef long long ll;
typedef long double ld;
typedef double db;
typedef string str;
typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;
#define mp make_pair
#define f first
#define s second
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<ld> vd;
typedef vector<str> vs;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<pd> vpd;
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) (x).rbegin(), (x).rend()
#define rsz resize
#define ins insert
#define ft front()
#define bk back()
#define pf push_front
#define pb push_back
#define eb emplace_back
#define lb lower_bound
#define ub upper_bound
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
const int MOD = 1e9+7; // 998244353; // = (119<<23)+1
const int MX = 6e3+5;
const ll INF = 1e18;
const ld PI = 4*atan((ld)1);
const int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};
ll vis[MX];
ll vis2[MX];
ll cl, cr;
vector<ll> adj[MX];
void dfs1(ll u) {
trav(v, adj[u]) {
if (!vis[v] && v>=cl) {
vis[v] = true;
dfs1(v);
}
}
}
void dfs2(ll u) {
trav(v, adj[u]) {
if (!vis2[v] && v<=cr) {
vis2[v] = true;
dfs2(v);
}
}
}
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> R) {
int Q = S.size();
F0R (i, sz(X)) {
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
std::vector<int> A(Q);
for (int i = 0; i < Q; ++i) {
memset(vis, 0, sizeof(vis));
memset(vis2, 0, sizeof(vis2));
cl = L[i];
cr = R[i];
if (S[i]>=L[i]) {
vis[S[i]] = true;
dfs1(S[i]);
}
if (E[i]<=R[i]) {
vis2[E[i]] = true;
dfs2(E[i]);
}
bool cango = false;
F0R (j, N) {
if (vis[j] && vis2[j] && j >= cl && j <= cr) {
cango = true;
break;
}
}
if (vis[E[i]]) {
cango = true;
}
A[i] = cango;
}
return A;
}
