#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int mxN = 2e5 + 12;
const int mxN2 = 6e5 + 12;
vector<int> adj[mxN];
struct DSU {
int dsu[mxN2];
int in[mxN2], out[mxN2];
vector<int> adj[mxN2];
vector<int> order;
int n;
int timer;
DSU(int _n) : n(_n) {
iota(dsu, dsu+mxN2, 0);
order.push_back(mxN2);
timer = 0;
}
int findSet(int u) {
if(u == dsu[u])
return u;
return dsu[u] = findSet(dsu[u]);
}
void unite(int u, int v) {
u = findSet(u);
v = findSet(v);
if(u == v)
return;
dsu[u] = dsu[v] = dsu[n] = n;
adj[n].push_back(u);
adj[n].push_back(v);
++n;
}
void dfs(int s) {
order.push_back(s);
in[s] = ++timer;
for(auto e : adj[s]) {
dfs(e);
}
out[s] = timer;
}
};
int ft[mxN2];
void update(int i, int x) {
for(; i < mxN2; i += i&-i)
ft[i] += x;
}
int query(int i) {
int r = 0;
for(; i; i -= i&-i)
r += ft[i];
return r;
}
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 n = N;
int m = (int)X.size();
int q = (int)S.size();
for(int i = 0; i < m; ++i) {
adj[X[i]].push_back(Y[i]);
adj[Y[i]].push_back(X[i]);
}
vector<int> queryL[mxN];
vector<int> queryR[mxN];
for(int i = 0; i < q; ++i) {
queryL[L[i]].push_back(i);
queryR[R[i]].push_back(i);
}
DSU levi(n);
for(int i = n-1; ~i; --i) {
for(auto e : adj[i]) {
if(e > i)
levi.unite(i, e);
}
for(auto z : queryL[i]) {
S[z] = levi.findSet(S[z]);
}
}
levi.dfs(levi.findSet(0));
DSU desni(n);
for(int i = 0; i < n; ++i) {
for(auto e : adj[i]) {
if(i > e)
desni.unite(i, e);
}
for(auto z : queryR[i]) {
E[z] = levi.findSet(E[z]);
}
}
desni.dfs(desni.findSet(n-1));
vector<pair<int, int>> doga[mxN2];
for(int i = 0; i < q; ++i) {
doga[levi.in[S[i]] - 1].push_back({i, -1});
doga[levi.out[S[i]]].push_back({i, 1});
}
vector<int> ans(q);
for(int i = 0; i < levi.n; ++i) {
if(levi.order[i] < n)
update(desni.in[levi.order[i]], 1);
for(auto z : doga[i]) {
int izraz = query(desni.out[E[z.first]]) - query(desni.in[E[z.first]]-1);
ans[z.first] += izraz * z.second;
}
}
for(auto &z : ans)
z = (z > 0);
return ans;
}
