#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
struct DMin {
vector<int> p, r;
DMin(int n, vector<int> &pr) : p(n) {
for (int i=0;i<n;i++) {
p[i]=i;
}
r=pr;
}
int get(int i) {
if (i != p[i])p[i]=get(p[i]);
return p[i];
}
void unite(int a, int b) {
a=get(a);b=get(b);
if (r[a] > r[b])swap(a,b);
p[b]=a;
}
};
struct DMax {
vector<int> p, r;
DMax(int n, vector<int> &pr) : p(n) {
for (int i=0;i<n;i++) {
p[i]=i;
}
r=pr;
}
int get(int i) {
if (i != p[i])p[i]=get(p[i]);
return p[i];
}
void unite(int a, int b) {
a=get(a);b=get(b);
if (r[a] < r[b])swap(a,b);
p[b]=a;
}
};
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) {
vector<vector<int>> g(N);
int M = X.size(), Q=S.size();
for (int i=0;i<M;i++) {
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
vector<int> ans(Q,0);
if (N <= 3000 && M <= 6000 && Q <= 3000) {
for (int i=0;i<Q;i++) {
vector<bool> vis1(N, false), vis2(N, false);
function<void(int)> dfs1=[&](int node) {
vis1[node]=true;
for (auto &x:g[node]) {
if (x >= L[i] && !vis1[x]) dfs1(x);
}
};
function<void(int)> dfs2=[&](int node) {
vis2[node]=true;
for (auto &x:g[node]) {
if (x <= R[i] && !vis2[x]) dfs2(x);
}
};
dfs1(S[i]);dfs2(E[i]);
for (int j=L[i];j<=R[i];j++) {
if (vis1[j] && vis2[j]) {
ans[i]=true;break;
}
}
}
return ans;
}
// first find node with degree one
int node = -1;
for (int i=0;i<N;i++) {
if (g[i].size() == 1) node = i;
}
vector<int> order(N, 0);
function<void(int,int)> dfs=[&](int nd, int parent) {
for (auto &x:g[nd]) {
if (x == parent) continue;
order[x] = order[nd]+1;
dfs(x, nd);
}
};
dfs(node, -1);
DMin dmn(N, order);
DMax dmx(N, order);
vector<int> far(Q, -1);
vector<vector<int>> newl(N), newr(N);
for (int i=0;i<Q;i++) {
newl[L[i]].push_back(i);
newr[R[i]].push_back(i);
}
for (int i=N-1;i>=0;i--) {
for (auto &x:g[i]) {
if (x > i) {
dmn.unite(x, i);
dmx.unite(x, i);
}
}
for (auto &x : newl[i]) {
if (order[S[x]] < order[E[x]]) {
far[x] = dmx.get(S[x]);
}
else {
far[x] = dmn.get(S[x]);
}
}
}
DMin dmn2(N, order);
DMax dmx2(N, order);
for (int i=0;i<N;i++) {
for (auto &x:g[i]) {
if (x < i) {
dmn2.unite(x, i);
dmx2.unite(x, i);
}
}
for (auto &x : newr[i]) {
int far2;
if (order[S[x]] < order[E[x]]) {
far2 = dmn2.get(E[x]);
if (order[far[x]] >= order[far2]) ans[x]=true;
}
else {
far2 = dmx2.get(E[x]);
if (order[far[x]] <= order[far2]) ans[x]=true;
}
}
}
return ans;
}
