#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int maxn = 200010;
int N, M, Q, S, E, L, R;
vector<int> adj[maxn];
int line[maxn];
int lineidx[maxn];
void dfs(int u, int p, vector<int>& vec) {
vec.push_back(u);
for (int v : adj[u]) {
if (v != p) {
dfs(v, u, vec);
}
}
}
pii tree[4*maxn];
inline void merge(pii& v, pii& l, pii& r) {
v.first = min(l.first, r.first);
v.second = max(l.second, r.second);
}
void build(int v, int tl, int tr) {
if (tl == tr) {
tree[v].first = tree[v].second = line[tl];
} else {
int tm = (tl + tr) / 2;
build(2*v, tl, tm);
build(2*v+1, tm+1, tr);
merge(tree[v], tree[2*v], tree[2*v+1]);
}
}
pii getrange(int v, int tl, int tr, int idx, bool type) {
if (type == false ? tree[v].first >= L : tree[v].second <= R) {
return pii(tl, tr);
} else if (tl == tr) {
return pii(-1, -1);
} else {
int tm = (tl + tr) / 2;
if (idx <= tm) { // target is on left side
pii res1 = getrange(2*v, tl, tm, idx, type);
if (res1.first == -1) {
return pii(-1, -1);
} else if (res1.second < tm) { // didn't reach right child
return res1;
} else { // may expand to right side
pii res2 = getrange(2*v+1, tm+1, tr, tm+1, type);
if (res2.first == -1) {
return res1;
} else {
return pii(res1.first, res2.second);
}
}
} else { // target is on right side
pii res1 = getrange(2*v+1, tm+1, tr, idx, type);
if (res1.first == -1) {
return pii(-1, -1);
} else if (res1.first > tm+1) { // didn't reach left child
return res1;
} else { // may expand to left side
pii res2 = getrange(2*v, tl, tm, tm, type);
if (res2.first == -1) {
return res1;
} else {
return pii(res2.first, res1.second);
}
}
}
}
}
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) {
N = _N;
M = _X.size();
Q = _S.size();
vector<int> A(Q);
for (int i = 0; i < M; ++i) {
++_X[i], ++_Y[i];
adj[_X[i]].push_back(_Y[i]);
adj[_Y[i]].push_back(_X[i]);
}
for (int i = 0; i < Q; ++i) {
++_S[i], ++_E[i], ++_L[i], ++_R[i];
}
if (M > N-1) {
vector<int> status(N+1);
for (int query = 0; query < Q; ++query) {
S = _S[query], E = _E[query], L = _L[query], R = _R[query];
status.assign(N+1, 0);
queue<int> q;
if (S >= L) {
q.push(S);
status[S] |= 1;
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
if (v >= L && status[v] == 0) {
status[v] |= 1;
q.push(v);
}
}
}
int intersection = -1;
if (E <= R) {
q.push(E);
status[E] |= 2;
}
while (!q.empty()) {
int u = q.front();
q.pop();
if (status[u] == 3) {
intersection = u;
break;
}
for (int v : adj[u]) {
if (v <= R && (status[v] == 0 || status[v] == 1)) {
status[v] |= 2;
q.push(v);
}
}
}
if (intersection == -1) {
A[query] = 0;
} else {
A[query] = 1;
}
}
} else {
vector<int> v1, v2;
if (adj[1].size() == 1) {
dfs(adj[1][0], 1, v1);
} else {
dfs(adj[1][0], 1, v1);
dfs(adj[1][1], 1, v2);
}
reverse(v1.begin(), v1.end());
for (int i = 0; i < (int)v1.size(); ++i) {
line[1+i] = v1[i];
}
line[v1.size()] = 1;
for (int i = 0; i < (int)v2.size(); ++i) {
line[1+v1.size()+1+i] = v2[i];
}
for (int i = 1; i <= N; ++i) {
lineidx[line[i]] = i;
}
build(1, 1, N);
for (int query = 0; query < Q; ++query) {
S = _S[query], E = _E[query], L = _L[query], R = _R[query];
pii range1 = getrange(1, 1, N, lineidx[S], false);
pii range2 = getrange(1, 1, N, lineidx[E], true);
int l = max(range1.first, range2.first);
int r = min(range1.second, range2.second);
// cout << "S=" << S << " E=" << E << " L=" << L << " R=" << R << "\n";
// cout << "Srange=[" << range1.first << "," << range1.second << "]\n";
// cout << "Erange=[" << range2.first << "," << range2.second << "]\n";
if (l <= r) {
A[query] = 1;
} else {
A[query] = 0;
}
}
}
return A;
}
