#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1,(n))
#define f first
#define s second
#define pb push_back
typedef vector<int> vi;
typedef pair<int, int> pii;
const int MAXN = 200100, MAXK = 20;
bool vis[MAXN];
bool ok = false;
vi adj[MAXN];
int cnt[MAXN];
void dfs (int v, int l, int r) {
vis[v] = true;
cnt[v]++;
for (int u : adj[v]) {
if (l <= u && u <= r && !vis[u])
dfs(u, l, r);
}
}
int toId[MAXN];
int minST[MAXN][MAXK];
int maxST[MAXN][MAXK];
int lg[MAXN];
int n;
void precLine () {
int cur = 0;
FOR(i, 0, n-1) if ((int)adj[i].size() == 1) cur = i;
vi seq;
seq.pb(cur);
int p = -1;
while (true) {
int np = cur;
int ncur = -1;
for (int x : adj[cur])
if (x != p)
ncur = x;
if (ncur == -1) break;
cur = ncur;
p = np;
seq.pb(cur);
}
//cout << " seq: ";
//for (int x : seq) cout << x << " ";
//cout << endl;
FOR(i, 0, n-1) toId[seq[i]] = i;
FOR(i, 0, n-1) minST[i][0] = maxST[i][0] = seq[i];
lg[1] = 0;
FOR(i, 2, MAXN-1) lg[i] = lg[i/2] + 1;
FOR(k, 1, MAXK-1) for (int i = 0; i + (1<<k) <= n; i++) {
minST[i][k] = min(minST[i][k-1], minST[i + (1<<(k-1))][k-1]);
maxST[i][k] = max(maxST[i][k-1], maxST[i + (1<<(k-1))][k-1]);
}
}
int getMin (int le, int ri) {
int k = lg[ri-le+1];
return min(minST[le][k], minST[ri - (1<<k) + 1][k]);
}
int getMax (int le, int ri) {
int k = lg[ri-le+1];
return max(maxST[le][k], maxST[ri - (1<<k) + 1][k]);
}
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();
n = N;
int m = (int)X.size();
std::vector<int> A(Q);
FOR(i, 0, m-1) {
int u = X[i], v = Y[i];
adj[u].pb(v);
adj[v].pb(u);
}
bool s3 = true;
if (m != n-1) s3 = false;
FOR(i, 0, n-1) if ((int)adj[i].size() > 2) s3 = false;
if (s3) {
precLine ();
FOR(i, 0, Q-1) {
int fr1, to1, fr2, to2;
int le, ri;
le = 0, ri = toId[S[i]];
while (le < ri) {
int mid = (le+ri)/2;
if (getMin(mid, S[i]) < L[i]) le = mid+1;
else ri = mid;
}
fr1 = le;
le = toId[S[i]], ri = n-1;
while (le < ri) {
int mid = (le+ri+1)/2;
if (getMin(S[i], mid) < L[i]) ri = mid-1;
else le = mid;
}
to1 = le;
le = 0, ri = toId[E[i]];
while (le < ri) {
int mid = (le+ri)/2;
if (getMax(mid, S[i]) > R[i]) le = mid+1;
else ri = mid;
}
fr2 = le;
le = toId[E[i]], ri = n-1;
while (le < ri) {
int mid = (le+ri+1)/2;
if (getMax(S[i], mid) > L[i]) ri = mid-1;
else le = mid;
}
to2 = le;
A[i] = (fr1 <= to2) && (fr2 <= to1);
}
} else {
for (int i = 0; i < Q; ++i) {
ok = false;
FOR(j, 0, n-1) cnt[j] = 0;
FOR(j, 0, n-1) vis[j] = 0;
dfs (S[i], L[i], n-1);
FOR(j, 0, n-1) vis[j] = 0;
dfs (E[i], 0, R[i]);
FOR(j, 0, n-1) if (cnt[j] > 1) ok = true;
A[i] = ok;
//cout << " ans: " << A[i] << endl;
}
}
return A;
}
