#include "werewolf.h"
#include <algorithm>
#include <functional>
template<typename T> bool ckmax(T& a, const T& b) {return b>a?a=b,1:0;}
template<typename T> bool ckmin(T& a, const T& b) {return b<a?a=b,1:0;}
const int MN = 2e5+10;
const int MQ = 2e5+10;
int N, M, Q;
std::vector<int> a[MN], ans;
struct ST
{
public:
std::vector<int> v;
int S;
ST(int _S): S(_S), v(_S*4, 0) {}
void build(int n, int l, int r, const std::vector<int>& line)
{
if(r-l>1)
{
int m = l+(r-l)/2;
build(n<<1, l, m, line);
build(n<<1|1, m, r, line);
v[n]=std::min(v[n<<1], v[n<<1|1]);
}
else
v[n]=line[l];
}
void build(const std::vector<int>& line) {build(1, 0, S, line);}
int qryr(int n, int l, int r, int qr, int cut) //rightmost point < cut
{
if(v[n]>=cut) return l-1;
if(r-l>1)
{
int m=l+(r-l)/2, f=m-1;
if(m < qr) f = qryr(n<<1|1, m, r, qr, cut);
if(f == m-1) return qryr(n<<1, l, m, qr, cut);
return f;
}
return l;
}
int qryr(int qr, int cut) {return qryr(1, 0, S, qr, cut);}
int qryl(int n, int l, int r, int ql, int cut) //leftmost point < cut
{
if(v[n]>=cut) return r;
if(r-l>1)
{
int m=l+(r-l)/2, f=m;
if(ql < m) f = qryl(n<<1, l, m, ql, cut);
if(f == m) return qryl(n<<1|1, m, r, ql, cut);
return f;
}
return l;
}
int qryl(int ql, int cut) {return qryl(1, 0, S, ql, cut);}
};
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) {
::N=N;
M=X.size();
Q = S.size();
ans.assign(Q, 0);
for(int i=0;i<M;++i)
{
a[X[i]].push_back(Y[i]);
a[Y[i]].push_back(X[i]);
}
bool is_line = M+1 == N;
for(int i=0;i<N && is_line;++i)
is_line &= a[i].size() <= 2;
if(is_line)
{
int st = -1;
for(int i=0;st == -1;++i)
if(a[i].size() == 1) st = i;
std::vector<int> line, wh(N, -1);
std::vector<char> vis(N, 0);
line.push_back(st);
for(int i=1;i<N;++i)
{
int n=line.back();
vis[n]=1;
for(int x:a[n])
if(!vis[x])
line.push_back(x);
}
for(int i=0;i<N;++i) wh[line[i]]=i;
ST hu(N), ww(N);
hu.build(line);
for(int& x:line) x*=-1;
ww.build(line);
for(int i=0;i<Q;++i)
{
int s=wh[S[i]], e=wh[E[i]];
if(s<e)
ans[i]=hu.qryl(s, L[i]) > ww.qryr(e, -R[i])+1;
else
ans[i]=ww.qryl(e, -R[i]) > hu.qryr(s, L[i])+1;
}
return ans;
}
for(int i=0;i<Q;++i)
{
std::vector<char> vh(N, 0), vw(N, 0);
std::function<void(int)> dfs=[&](int n)
{
vh[n]=1;
for(int x:a[n])
if(!vh[x] && x >= L[i])
dfs(x);
};
dfs(S[i]);
dfs = [&](int n)
{
vw[n]=1;
for(int x:a[n])
if(!vw[x] && x <= R[i])
dfs(x);
};
dfs(E[i]);
for(int j=0;!ans[i] && j<N;++j)
{
//printf("%d: %d: [%d/%d]\n", i, j, vh[j], vw[j]);
ans[i] |= vh[j] && vw[j];
}
}
return ans;
}
