#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
using ll = long long;
const int mxN = 2e5+10;
int p[mxN], tin[mxN], tout[mxN], cnt = -1;
bool added[mxN];
vector<int> adj[mxN], adj1[mxN];
set<int> s[mxN];
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 uni1(int a, int b) {
if(s[b].size() < s[a].size()) swap(s[a], s[b]);
for(auto it : s[a]) s[b].insert(it);
p[a] = p[b] = b;
}
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]);
}
vector<vector<array<int, 3>>> queries(n+1);
vector<vector<array<int, 2>>> queries_r(n+1);
int q = L.size();
for(int i = 0; i < q; i++) {
queries[L[i]].push_back({R[i], S[i], i});
queries_r[R[i]].push_back({E[i], i});
}
for(int i = 0; i < n; i++) {
added[i] = true;
for(auto it : adj[i]) {
if(added[it]) {
int par = get(it);
uni(par, i);
}
}
}
vector<int> ans(q);
dfs(n-1, n-1);
for(int i = 0; i < n; i++) {
for(auto [it, idx] : queries_r[i]) {
if(tin[i] <= tin[it] && tin[it] <= tout[i]) ans[idx] = 1;
}
}
iota(p, p+n+1, 0); memset(added, false, sizeof added);
for(int i = 0; i < n; i++) s[i].insert(i);
for(int i = n-1; i >= 0; i--) {
added[i] = true;
for(auto it : adj[i]) {
if(added[it]) {
int par = get(it);
uni1(par, i);
}
}
for(auto [it, st, idx] : queries[i]) {
if(s[i].count(st) == 0) ans[idx] = 0;
auto it1 = s[i].lower_bound(tin[it]);
if(it1 != s[i].end() && *it1 <= tout[it]) ans[idx] = ans[idx] & 1;
else ans[idx] = 0;
}
}
return ans;
}
/*int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
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;
}*/
