#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
struct DSU {
vector<int> p;
DSU(int n=0){ init(n); }
void init(int n){
p.resize(n+1);
iota(p.begin(), p.end(), 0);
}
int find(int x){
return p[x] == x ? x : p[x] = find(p[x]);
}
void unite(int a, int b){
a = find(a);
b = find(b);
if(a != b) p[b] = a;
}
};
static inline long long pack_pair(int a, int b){
return ( (long long)a << 32 ) ^ (unsigned long long)b;
}
vector<int> check_validity(
int N,
vector<int> X,
vector<int> Y,
vector<int> S,
vector<int> E,
vector<int> L,
vector<int> R
){
int M = X.size();
int Q = S.size();
// adjacency list
vector<vector<int>> g(N+1);
for(int i = 0; i < M; i++){
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
// -------- DSU for human form (cities >= threshold) --------
DSU dsuH(N);
vector<int> compH(N+1);
vector<char> active(N+1, 0);
for(int v = N; v >= 1; v--){
active[v] = 1;
for(int nx : g[v]) if(active[nx]) dsuH.unite(v, nx);
compH[v] = dsuH.find(v);
}
// -------- DSU for wolf form (cities <= threshold) --------
DSU dsuW(N);
fill(active.begin(), active.end(), 0);
vector<int> compW(N+1);
for(int v = 1; v <= N; v++){
active[v] = 1;
for(int nx : g[v]) if(active[nx]) dsuW.unite(v, nx);
compW[v] = dsuW.find(v);
}
// -------- compress pairs (compH, compW) --------
unordered_map<long long, int> mp;
mp.reserve(N * 2);
vector<int> id(N+1);
int idCnt = 0;
for(int v = 1; v <= N; v++){
long long key = pack_pair(compH[v], compW[v]);
if(!mp.count(key)){
mp[key] = ++idCnt;
}
id[v] = mp[key];
}
// store positions for each id
vector<vector<int>> pos(idCnt + 1);
for(int v = 1; v <= N; v++) pos[id[v]].push_back(v);
for(int i = 1; i <= idCnt; i++) sort(pos[i].begin(), pos[i].end());
// -------- answer queries --------
vector<int> ans(Q, 0);
for(int i = 0; i < Q; i++){
int s = S[i], e = E[i], l = L[i], r = R[i];
// T must satisfy (l < T < r)
if(!(l + 1 < r)){
ans[i] = 0;
continue;
}
long long key = pack_pair(compH[s], compW[e]);
if(!mp.count(key)){
ans[i] = 0;
continue;
}
int myId = mp[key];
auto &vec = pos[myId];
// find smallest T >= l+1
auto it = lower_bound(vec.begin(), vec.end(), l + 1);
if(it != vec.end() && *it < r)
ans[i] = 1;
else
ans[i] = 0;
}
return ans;
}
