#include "werewolf.h"
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll, ll>
#define pb push_back
#define epb emplace_back
#define ull unsigned ll
using namespace std;
const int nmax = 200001;
/*6 6 3
5 1
1 2
1 3
3 4
3 0
5 2
4 2 1 2
4 2 2 2
5 4 3 4
*/
vector <int> p(nmax);
void make_set(int v){
p[v]= v;
}
int find_set(int v){
return p[v] == v ? v : p[v] = find_set(p[v]);
}
vector <int> g[nmax][2];
void union_sets(int a, int b, int ind){
a = find_set(a);
b = find_set(b);
if(a == b)
return;
p[b] = a;
g[a][ind].pb(b);
}
vector <int> eu[2];
int in[nmax][2], sz[nmax][2];
int timer = 1;
void dfs(int v, int e, int ind){
eu[ind].pb(v);
in[v][ind] = timer++;
sz[v][ind] = 1;
for(int to : g[v][ind]){
if(to != e)
dfs(to, v, ind), sz[v][ind] += sz[to][ind];
}
}
int t[4 * nmax];
void update(int v, int l, int r, int pos, int val){
if(l > pos || r < pos)
return;
if(l == r){
t[v] = val;
return;
}
int m = (l + r) / 2;
update(2 * v, l, m, pos, val);
update(2 * v + 1, m + 1, r, pos, val);
t[v] = min(t[2 * v], t[2 * v+ 1]);
}
int get(int v, int l, int r, int st, int fin){
if(l > fin || r < st)
return 1e9;
if(l >= st && r <= fin)
return t[v];
int m = (l + r) / 2;
return min(get(2 * v, l, m, st, fin), get(2 * v + 1, m + 1, r, st, fin));
}
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();
vector <vector <int> > G(n);
vector <vector <int> > vec(n);
vector <int> a(q);
vector <int> b(q);
for(int i = 0; i < x.size(); i++){
int u = x[i], v = y[i];
G[u].pb(v);
G[v].pb(u);
}
for(int i = 0; i < r.size(); i++){
vec[r[i]].pb(i);
}
for(int i = 0; i < n; i++){
make_set(i);
}
for(int i = 0; i < n; i++){
for(int to : G[i]){
if(i > to)
union_sets(i, to, 0);
}
for(int to : vec[i]){
a[to] = find_set(e[to]);
}
}
for(int i = 0; i < n; i++){
vec[i].clear();
make_set(i);
}
for(int i = 0; i < l.size(); i++){
vec[l[i]].pb(i);
}
for(int i = n - 1; i >= 0; --i){
for(int to : G[i]){
if(i < to)
union_sets(i, to, 1);
}
for(int to : vec[i]){
b[to] = find_set(s[to]);
}
}
eu[0].pb(-1);
eu[1].pb(-1);
dfs(n - 1, n - 1, 0);
timer = 1;
dfs(0, 0, 1);
vector <vector <pair<pii, pii> > > qv(n + 1);
for(int i = 0; i < q; i++){
int l = in[a[i]][0];
int r = in[a[i]][0] + sz[a[i]][0] - 1;
int L = in[b[i]][1];
int R = in[b[i]][1] + sz[b[i]][1] - 1;
qv[l].pb({{r, i}, {L, R}});
}
for(int i = 1; i <= n; ++i){
int x = in[eu[1][i]][0];
update(1, 1, n, i, x);
}
vector <int> ans(q);
for(int i = 1; i <= n; i++){
for(auto to : qv[i]){
int r = to.f.f, ind = to.f.s;
int L = to.s.f, R = to.s.s;
if(get(1, 1, n, L, R) > r) ans[ind] = 0;
else ans[ind] = 1;
}
update(1, 1, n, in[eu[0][i]][1], 1e9);
}
return ans;
}
