#include "werewolf.h"
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <numeric>
using namespace std;
const int N = 2e5 + 5;
int dsu[N], sz[N], hd[N], tin[N], tout[N], tiktak = 0;
vector <vector<int> > g, tmp, child[2], query;
vector <int> ans;
int get(int x) {
return x == dsu[x] ? x : dsu[x] = get(dsu[x]);
}
void merge(int x, int y, int id) {
x = get(x);
y = get(y);
if (x == y)
return;
if (sz[y] > sz[x])
swap(x, y);
dsu[y] = x;
child[id][x].push_back(y);
}
void dfs1(int v) {
tin[v] = ++tiktak;
for (auto to : child[1][v]) {
dfs1(to);
}
tout[v] = tiktak;
}
set <int> st[N];
void dfs0(int v) {
for (auto to : child[0][v]) {
dfs0(to);
if (st[to].size() > st[v].size())
st[v].swap(st[to]);
for (auto x : st[to]) {
st[v].insert(x);
}
}
st[v].insert(tin[v]);
for (auto to : query[v]) {
auto it = st[v].lower_bound(tin[hd[to]]);
if (it != st[v].end() && *it <= tout[hd[to]]) {
ans[to] = 1;
}
}
}
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();
g.resize(N);
child[0].resize(N);
child[1].resize(N);
query.resize(N);
ans.resize(Q, 0);
for (int i = 0; i < X.size(); i++) {
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
iota(dsu, dsu + N, 0);
fill(sz, sz + N, 1);
tmp.clear();
tmp.resize(N);
for (int i = 0; i < Q; i++) {
tmp[R[i]].push_back(i);
}
for (int i = 0; i < N; i++) {
for (auto j : g[i]) {
if (i > j)
merge(i, j, 1);
}
for (auto j : tmp[i]) {
hd[j] = get(E[j]);
}
}
iota(dsu, dsu + N, 0);
fill(sz, sz + N, 1);
tmp.clear();
tmp.resize(N);
for (int i = 0; i < Q; i++) {
tmp[L[i]].push_back(i);
}
for (int i = N - 1; i >= 0; i--) {
for (auto j : g[i]) {
if (i < j)
merge(i, j, 0);
}
for (auto j : tmp[i]) {
query[get(S[j])].push_back(j);
}
}
dfs1(N - 1);
dfs0(0);
return ans;
}
/*
6 6
5 1
1 2
1 3
3 4
3 0
5 2
3
4 2 1 2
4 2 2 2
5 4 3 4
*/
