#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
using ll = long long;
const int mxN = 5e5+10;
int p[mxN], tin[mxN], tout[mxN], cnt = -1, tin1[mxN], tout1[mxN];
bool added[mxN];
vector<int> adj[mxN], adj1[mxN];
int st[mxN*4];
void upd(int node, int l, int r, int k) {
if(l == r && l == k) {
st[node] = 1;
return ;
}
if(l > k || r < k) return ;
int mid = (l+r)/2;
upd(node*2, l, mid, k);
upd(node*2+1, mid+1, r, k);
st[node] = st[node*2] + st[node*2+1];
}
int qry(int node, int l, int r, int l1, int r1) {
if(l1 <= l && r <= r1) return st[node];
if(l1 > r || r1 < l) return 0;
int mid = (l+r)/2;
return qry(node*2, l, mid, l1, r1) + qry(node*2+1, mid+1, r, l1, r1);
}
int get(int x) {
return p[x] == x ? x : p[x] = get(p[x]);
}
void uni(int a, int b) {
p[a] = p[b] = b;
adj1[b].push_back(a);
}
void dfs(int node, int p) {
tin[node] = ++cnt;
for(auto it : adj1[node]) {
if(it == p) continue;
dfs(it, node);
}
tout[node] = cnt;
}
void dfs1(int node, int p) {
tin1[node] = ++cnt;
for(auto it : adj1[node]) {
if(it == p) continue;
dfs1(it, node);
}
tout1[node] = cnt;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
int M = X.size(); int n = N;
iota(p, p+n+1, 0);
for(int i = 0; i < M; i++) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
int q = L.size();
vector<vector<array<int, 2>>> queries_l(n+1);
vector<vector<array<int, 2>>> queries_r(n+1);
vector<int> root(q+1);
vector<array<array<int, 2>, 2>> ranges(q+1);
for(int i = 0; i < q; i++) {
queries_r[R[i]].push_back({E[i], i});
queries_l[L[i]].push_back({S[i], i});
}
for(int i = 0; i < n; i++) {
added[i] = true;
for(auto it : adj[i]) {
if(added[it]) {
int par = get(it);
if(par == i) continue;
uni(par, i);
}
}
for(auto [it, idx] : queries_r[i]) {
int par = get(it);
root[idx] = par;
}
}
dfs(n-1, n-1);
for(int i = 0; i < q; i++) {
ranges[i][0] = {tin[root[i]], tout[root[i]]};
}
memset(added, false, sizeof added); iota(p, p+n+1, 0);
for(int i = 0; i < n; i++) adj1[i].clear();
for(int i = n-1; i >= 0; i--) {
added[i] = true;
for(auto it : adj[i]) {
if(added[it]) {
int par = get(it);
if(par == i) continue;
uni(par, i);
}
}
for(auto [it, idx] : queries_l[i]) {
int par = get(it);
root[idx] = par;
}
}
cnt = -1;
dfs1(0, 0);
vector<int> ans(q, 0);
vector<int> past(q+1, 0);
vector<vector<array<int, 4>>> queries(n);
for(int i = 0; i < q; i++) {
ranges[i][1] = {tin1[root[i]], tout1[root[i]]};
if(ranges[i][0][0] - 1 != -1) queries[ranges[i][0][0]-1].push_back({-1, tin1[root[i]], tout1[root[i]], i});
queries[ranges[i][0][1]].push_back({1, tin1[root[i]], tout1[root[i]], i});
}
vector<int> ord(n); iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int a, int b) {
return tin[a] < tin[b];
});
for(int i = 0; i < n; i++) {
upd(1, 0, n, tin1[ord[i]]);
for(auto [flag, l, r, idx] : queries[i]) {
if(flag == 1) {
int now = qry(1, 0, n, l, r);
if(now > past[idx]) ans[idx] = 1;
}
else {
int now = qry(1, 0, n, l, r);
past[idx] = now;
}
}
}
return ans;
}
/*int main()
{
vector<int> ans = check_validity(6, {5, 1, 1, 3, 3, 5}, {1, 2, 3, 4, 0, 2},
{4, 4, 5}, {2, 2, 4}, {1, 2, 3}, {2, 2, 4});
for(auto it : ans) {
cout << it << ' ';
}
return 0;
}*/
