#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define srt(x) sort(all(x))
typedef long long ll;
using vi = vector<int>;
using vl = vector<ll>;
struct DSU {
int n;
vi par, siz, fchange;
vector<set<int>> has;
int timer = 0;
// vi left, right;
DSU(int n) {
par.assign(n, 0); iota(all(par), 0);
siz.assign(n, 1);
fchange.assign(n, INT_MAX);
has.assign(n, set<int>());
FOR(i, 0, n) has[i].insert(i);
// left.assign(n, 1); iota(all(left), 0);
// right.assign(n, 1); iota(all(right), 0);
}
int find_set(int v, int time) {
if (fchange[v] > time || par[v] == v) return v;
// return par[v] = find_set(par[v]);
return find_set(par[v], time);
}
void union_set(int a, int b) {
a = find_set(a, timer);
b = find_set(b, timer);
if (a != b) {
// if (siz[b] > siz[a]) swap(a, b);
par[b] = a;
siz[a] += siz[b];
fchange[b] = timer++;
// if (has[b] > has[a]) swap(has[b], has[a]);
has[a].insert(all(has[b]));
// left[a] = min(left[a], left[b]);
// right[a] = min(right[a], right[b]);
}
}
};
/*
N = num nodes
X, Y = edges
S, E = start and end nodes
L, R = human and werewolf cities
*/
int n, m, q;
vi x, y, s, e, l, r;
vi queries;
vector<vi> adj;
bool dfs(int u, int L, int R, int target, vector<bool> &seen, bool reached_transform, bool reached_vampire) {
// cout << "At node " << u << " L, R = (" << L << ", " << R << ") target = " << target << " RT? " << reached_transform << " RV? " << reached_vampire << "\n";
if (u == target) {
// cout << "Reached " << target << " did we transform? " << reached_transform << "\n";
return reached_transform;
}
bool can = false;
seen[u] = true;
for (auto v : adj[u]) {
if (seen[v]) continue;
if (reached_vampire && v > R) continue;
if (!reached_transform && v < L) continue;
bool nt = reached_transform || (v >= L && v <= R);
bool nv = reached_vampire || (v < L);
can = can || dfs(v, L, R, target, seen, nt, nv);
if (can) break;
}
seen[u] = false;
return can;
}
int answer_query(int qn) {
// cout << "answering query " << qn << "\n";
int start = s[qn], end = e[qn];
vector<bool> seen(n, false);
return dfs(start, l[qn], r[qn], end, seen, start >= l[qn] && start <= r[qn], start < l[qn]);
}
void dfs_dp(int u, int p, vi &DP) {
DP[u] = u;
for (auto &v : adj[u]) {
if (v == p) continue;
dfs_dp(v, u, DP);
DP[u] = max(DP[u], DP[v]);
}
}
vi check_validity(int N, vi X, vi Y, vi S, vi E, vi L, vi R) {
n = N; x = X; y = Y; s = S; e = E; l = L; r = R;
m = x.size(), q = S.size();
adj.assign(n, vi());
FOR(i, 0, m) {
adj[X[i]].pb(Y[i]);
adj[Y[i]].pb(X[i]);
}
queries.assign(q, 0); iota(all(queries), 0);
// sort(all(queries), [&](int a, int b) {return L[a] > L[b];});
vi A(q);
auto blueDSU = DSU(n);
auto redDSU = DSU(n);
vi wB(m), wR(m); iota(all(wB), 0); iota(all(wR), 0);
FOR(i, 0, m) {
wR[i] = max(X[i], Y[i]);
wB[i] = min(X[i], Y[i]);
}
sort(all(wR), [&](int a, int b) {return max(X[a], Y[a]) < max(X[b], Y[b]);});
sort(all(wB), [&](int a, int b) {return min(X[a], Y[a]) < min(X[b], Y[b]);}); reverse(all(wB));
for (auto &edge : wR) {
redDSU.union_set(X[edge], Y[edge]);
}
for (auto &edge : wB) {
blueDSU.union_set(X[edge], Y[edge]);
}
/*
line case:
process queries in decreasing order of L[i]
blueDSU
*/
// vi pthmax(n, INT_MIN);
// dfs_dp(0, 0, pthmax);
int curedge = 0;
// for (auto query : queries) {
// int cidx = wB[curedge];
// while (min(X[cidx], Y[cidx]) >= L[query]) {
// blueDSU.union_set(X[cidx], Y[cidx]);
// curedge++;
// cidx = wB[curedge];
// }
// tried:
//[1, 3, 5, 7]
// int en = E[query]; // 1
// int en = S[query]; // 2
// int sn = E[query]; // 3
// int sn = S[query]; // 4
// int et = L[query]; // 5
// int et = R[query]; // 6
// int st = L[query]; // 7
// int st = R[query]; // 8
// for (auto en : {E, S}) {
// for (auto sn : {E, S}) {
// for (auto et : {L, R}) {
// for (auto st : {L, R}) {
// for (auto query : queries) {
FOR(query, 0, q) {
auto en = E;
auto sn = S;
auto et = R;
auto st = L;
set<int> s1 = redDSU.has[redDSU.find_set(en[query], et[query])];
set<int> s2 = blueDSU.has[blueDSU.find_set(sn[query], st[query])];
bool found = false;
for (auto &el : s1) {
if (s2.count(el)) {
// cout << "1\n";
// found = true;
A[query] = 1;
break;
}
}
// if (!found) cout << "0\n";
}
// cout << "\n";
// }}}}
// }
FOR(i, 0, q) A[i] = 1 - A[i];
return A;
}
