#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 400005;
int n, m, qq;
vector<int> g[N];
void dfs(int x, int ul, int ur, vector<bool>& c)
{
if (!(ul <= x && x <= ur))
return;
if (c[x])
return;
c[x] = true;
for (int i = 0; i < g[x].size(); ++i)
{
int h = g[x][i];
dfs(h, ul, ur, c);
}
}
pair<int, int> t[N * 4];
pair<int, int> mer(const pair<int, int>& l, const pair<int, int>& r)
{
return m_p(min(l.fi, r.fi), max(l.se, r.se));
}
void ubd(int tl, int tr, int x, int y, int pos)
{
if (tl == tr)
{
t[pos] = m_p(y, y);
return;
}
int m = (tl + tr) / 2;
if (x <= m)
ubd(tl, m, x, y, pos * 2);
else
ubd(m + 1, tr, x, y, pos * 2 + 1);
t[pos] = mer(t[pos * 2], t[pos * 2 + 1]);
}
pair<int, int> qry(int tl, int tr, int l, int r, int pos)
{
if (l > r)
return m_p(n, 0);
if (tl == l && tr == r)
{
return t[pos];
}
int m = (tl + tr) / 2;
return mer(qry(tl, m, l, min(m, r), pos * 2),
qry(m + 1, tr, max(m + 1, l), r, pos * 2 + 1));
}
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 = sz(X);
qq = sz(S);
for (int i = 0; i < m; ++i)
{
int x = X[i];
int y = Y[i];
g[x].push_back(y);
g[y].push_back(x);
}
vector<int> ans;
/*if (n <= 3000 && m <= 6000 && qq <= 3000)
{
for (int i = 0; i < qq; ++i)
{
vector<bool> cs, ce;
cs.assign(n, false);
ce.assign(n, false);
dfs(S[i], L[i], n - 1, cs);
dfs(E[i], 0, R[i], ce);
for (int x = 0; x < n; ++x)
{
if (cs[x] && ce[x])
{
ans.push_back(1);
break;
}
}
if (sz(ans) != (i + 1))
ans.push_back(0);
}
return ans;
}*/
vector<int> v;
for (int x = 0; x < n; ++x)
{
if (sz(g[x]) != 1)
continue;
vector<bool> c;
c.assign(n, false);
c[x] = true;
v.push_back(x);
while (1)
{
int nx = x;
for (int i = 0; i < g[x].size(); ++i)
{
int h = g[x][i];
if (!c[h])
{
x = h;
break;
}
}
if (x == nx)
break;
c[x] = true;
v.push_back(x);
}
break;
}
vector<int> u(n);
for (int i = 0; i < n; ++i)
{
u[v[i]] = i;
ubd(0, n - 1, i, v[i], 1);
}
for (int i = 0; i < qq; ++i)
{
if (u[S[i]] < u[E[i]])
{
int l = u[S[i]], r = n - 1;
int uu;
while (l <= r)
{
int m = (l + r) / 2;
if (qry(0, n - 1, u[S[i]], m, 1).fi >= L[i])
{
uu = m;
l = m + 1;
}
else
r = m - 1;
}
if (qry(0, n - 1, uu, u[E[i]], 1).se <= R[i])
ans.push_back(1);
else
ans.push_back(0);
}
else
{
int l = u[E[i]], r = n - 1;
int uu;
while (l <= r)
{
int m = (l + r) / 2;
if (qry(0, n - 1, u[E[i]], m, 1).se <= R[i])
{
uu = m;
l = m + 1;
}
else
r = m - 1;
}
if (qry(0, n - 1, uu, u[S[i]], 1).fi >= L[i])
ans.push_back(1);
else
ans.push_back(0);
}
}
return ans;
}
