#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, int> pli;
const int MAXN = 2e5 + 5;
struct dsu {
int dad[MAXN];
vector <int> comp[MAXN];
vector <pii> events[MAXN];
void init(int n, int t) {
for (int i = 1; i <= n; i++) {
events[i].push_back({t, i});
comp[i].push_back(i);
dad[i] = i;
}
}
void join(int x, int y) {
int timer = x;
x = dad[x];
y = dad[y];
if (x == y)
return;
if (comp[x].size() > comp[y].size())
swap(x, y);
for (auto it : comp[x]) {
events[it].push_back({timer, y});
comp[y].push_back(it);
dad[it] = y;
}
}
};
dsu up, down;
vector <int> adj[MAXN];
unordered_map <ll, int> mx, has;
vector <int> p[MAXN], f[MAXN];
vector <pli> q[MAXN];
pii where[MAXN];
void inc(vector <int> &v) {
for (auto &it : v)
it++;
}
inline ll hsh(pii p) {
return (ll)MAXN * p.first + p.second;
}
vector <int> check_validity(int N, vector <int> x, vector <int> y, vector <int> st, vector <int> en, vector <int> l, vector <int> r) {
int M = x.size();
int Q = st.size();
inc(x);
inc(y);
inc(st);
inc(en);
inc(l);
inc(r);
for (int i = 0; i < M; i++) {
adj[x[i]].push_back(y[i]);
adj[y[i]].push_back(x[i]);
}
for (int i = 0; i < Q; i++)
p[r[i]].push_back(i);
up.init(N, 0);
for (int i = 1; i <= N; i++) {
for (auto it : adj[i])
if (it <= i)
up.join(i, it);
for (auto it : p[i])
where[it].first = up.dad[en[it]];
}
for (int i = 1; i <= N; i++)
p[i].clear();
for (int i = 0; i < Q; i++)
p[l[i]].push_back(i);
down.init(N, N + 1);
for (int i = N; i; i--) {
for (auto it : adj[i])
if (it >= i)
down.join(i, it);
for (auto it : p[i])
where[it].second = down.dad[st[it]];
}
for (int i = 0; i < Q; i++)
has[hsh(where[i])] = 1;
for (int i = 1; i <= N; i++)
for (auto it1 : up.events[i])
for (auto it2 : down.events[i]) {
ll tmp = hsh({it1.second, it2.second});
if (has[tmp])
q[it1.first].push_back({tmp, it2.first});
}
for (int i = 0; i < Q; i++)
f[r[i]].push_back(i);
vector <int> ans(Q, 0);
for (int i = 0; i <= N; i++) {
for (auto it : q[i])
if (it.second > mx[it.first])
mx[it.first] = it.second;
for (auto it : f[i])
ans[it] = mx[hsh(where[it])] >= l[it];
}
return ans;
}
