#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;
const int MAX_N = 200000;
vector<int> graph[MAX_N];
vector<pair<int, int> > components[MAX_N];
struct CompEdge {
int a, b, timestamp1, timestamp2;
};
vector<CompEdge> edges;
int currComp[MAX_N];
int sizeComp[MAX_N];
int poz[MAX_N];
void dfs(int nod, int oldComp, int newComp, int timestamp) {
sizeComp[oldComp]--;
sizeComp[newComp]++;
currComp[nod] = newComp;
components[nod].push_back(make_pair(newComp, timestamp));
for(auto it: graph[nod])
if(currComp[it] == oldComp)
dfs(it, oldComp, newComp, timestamp);
}
void mergeComps(int a, int b, int timestamp) {
if(sizeComp[currComp[a]] < sizeComp[currComp[b]])
swap(a, b);
dfs(b, currComp[b], currComp[a], timestamp);
}
void dfs2(int nod, int oldComp, int newComp, int timestamp) {
for(auto it: components[nod])
edges.push_back({it.first, newComp, it.second, timestamp});
sizeComp[oldComp]--;
sizeComp[newComp]++;
currComp[nod] = newComp;
for(auto it: graph[nod])
if(currComp[it] == oldComp)
dfs2(it, oldComp, newComp, timestamp);
}
void mergeComps2(int a, int b, int timestamp) {
if(sizeComp[currComp[a]] < sizeComp[currComp[b]])
swap(a, b);
dfs2(b, currComp[b], currComp[a], timestamp);
}
void dfs3(int nod, int oldComp, int newComp) {
sizeComp[oldComp]--;
sizeComp[newComp]++;
currComp[nod] = newComp;
for(auto it: graph[nod])
if(currComp[it] == oldComp)
dfs3(it, oldComp, newComp);
}
void mergeComps3(int a, int b) {
if(sizeComp[currComp[a]] < sizeComp[currComp[b]])
swap(a, b);
dfs3(b, currComp[b], currComp[a]);
}
int pozQ[MAX_N];
std::vector<int> LQ;
bool cmp(int a, int b) {
return LQ[a] > LQ[b];
}
unordered_map<int, int> firstTime[MAX_N];
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();
LQ = L;
std::vector<int> rez(Q);
for(int i = 0; i < Q; ++i)
pozQ[i] = i;
std::sort(pozQ, pozQ + Q, cmp);
for(int i = 0; i < X.size(); ++i) {
graph[X[i]].push_back(Y[i]);
graph[Y[i]].push_back(X[i]);
}
for(int i = 0; i < N; ++i) {
currComp[i] = i;
sizeComp[i] = 1;
}
for(int i = 0; i < N; ++i) {
components[i].push_back(make_pair(i, 0));
for(auto it: graph[i])
if(it < i && currComp[i] != currComp[it])
mergeComps(it, i, i);
}
for(int i = 0; i < N; ++i) {
currComp[i] = i;
sizeComp[i] = 1;
}
for(int i = N - 1; i >= 0; --i) {
for(auto it: components[i])
edges.push_back({it.first, i, it.second, i});
for(auto it: graph[i])
if(it > i && currComp[it] != currComp[i]) {
mergeComps2(it, i, i);
}
}
for(int i = 0; i < N; ++i) {
currComp[i] = i;
sizeComp[i] = 1;
}
int lastup = N - 1;
int lastE = 0;
for(int i = 0; i < Q; ++i) {
int l, r, s, e;
l = L[pozQ[i]];
r = R[pozQ[i]];
s = S[pozQ[i]];
e = E[pozQ[i]];
while(lastup >= l) {
for(auto it: graph[lastup])
if(lastup < it && currComp[lastup] != currComp[it])
mergeComps3(it, lastup);
--lastup;
}
while(lastE < edges.size() && edges[lastE].timestamp2 >= l) {
if(edges[lastE].timestamp2 <= edges[lastE].timestamp2) {
int a = edges[lastE].a, b = edges[lastE].b, ts = edges[lastE].timestamp1;
firstTime[a][b] = min(firstTime[a][b], ts - MAX_N);
}
++lastE;
}
int compS, compE = currComp[s];
int stB = 0, drB = components[e].size();
while(drB - stB > 1) {
int mid = (stB + drB) / 2;
if(components[e][mid].second <= r)
stB = mid;
else
drB = mid;
}
compS = components[e][stB].first;
if(firstTime[compS][compE] + MAX_N <= r)
rez[pozQ[i]] = true;
else
rez[pozQ[i]] = false;
}
return rez;
}
