#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
const int NAX = 4e5+10, LG = 20;
vector<int> edges[NAX], tree[2][NAX], arr[2];
int in[2][NAX], out[2][NAX], p[2][NAX], L[2][NAX][LG];
int timer;
void add_edge(int x, int y, int which) {
tree[which][x].push_back(y);
tree[which][y].push_back(x);
}
int find_set(int x, int which) {
return x == p[which][x] ? x : p[which][x] = find_set(p[which][x], which);
}
void union_sets(int x, int y, int which) {
x = find_set(x, which);
y = find_set(y, which);
if(x == y) {
return;
}
p[which][y] = x;
add_edge(x, y, which);
}
void dfs(int x, int p, int which) {
in[which][x] = ++timer;
L[which][x][0] = p;
arr[which].push_back(x);
for(int i = 1; i < LG; ++i) {
int up = L[which][x][i - 1];
L[which][x][i] = ~up ? L[which][up][i - 1] : -1;
}
for(int to : tree[which][x]) {
if(to != p) {
dfs(to, x, which);
}
}
out[which][x] = timer;
}
int up(int x, int cutoff, int p) {
for(int i = LG - 1; i >= 0; --i) {
if(p == 0 && ~L[p][x][i] && L[p][x][i] >= cutoff) {
x = L[p][x][i];
}
if(p == 1 && ~L[p][x][i] && L[p][x][i] <= cutoff) {
x = L[p][x][i];
}
}
return x;
}
vector<int> check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
for(int i = 0; i < X.size(); ++i) {
edges[X[i]].push_back(Y[i]);
edges[Y[i]].push_back(X[i]);
}
for(int i = 0; i < N; ++i) {
p[0][i] = p[1][i] = i;
}
for(int i = N - 1; i >= 0; --i) {
for(int to : edges[i]) {
if(to > i) {
union_sets(i, to, 0);
}
}
}
for(int i = 0; i < N; ++i) {
for(int to : edges[i]) {
if(to < i) {
union_sets(i, to, 1);
}
}
}
timer = -1; dfs(0, -1, 0);
timer = -1; dfs(N - 1, -1, 1);
int Q = S.size();
vi A(Q);
vi seen(N);
for(int i = 0; i < Q; ++i) {
int s = up(S[i], L[i], 0);
int e = up(E[i], R[i], 1);
for(int x = in[0][s]; x <= out[0][s]; ++x) {//slow af
seen[arr[0][x]] = 1;
}
for(int x = in[1][e]; x <= out[1][e]; ++x) {
if(seen[arr[1][x]]) {
A[i] = 1;
break;
}
}
for(int x = in[0][s]; x <= out[0][s]; ++x) {
seen[arr[0][x]] = 0;
}
}
return A;
}
