#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define REP(i, a, b) for (ll i=a; i<b; i++)
#define pb push_back
int ordem[200000];
vector<int> graph[200000];
int sparse_maximo[200000][20];
int sparse_minimo[200000][20];
int posicao[200000];
int visited[200000] = {};
queue<int> possiveis[2];
void dfs (int u, int indice, int type, int r, int l)
{
visited[u] = indice + 1;
for (auto v: graph[u])
{
if (visited[v] > indice)
continue;
if ((type == 0 && v >= l) || (type == 1 && v <= r && v >= l) || (type == 2 && v <= r))
{
if (type != 2)
possiveis[type].push (v);
dfs (v, indice, type, r, l);
}
}
}
void create (int N)
{
for (ll i=N-1; i>=0; i--)
{
sparse_maximo[i][0] = ordem[i];
sparse_minimo[i][0] = ordem[i];
REP(j, 1, 20)
{
if (i + (1<<j) > N)
break;
sparse_maximo[i][j] = max (sparse_maximo[i][j-1], sparse_maximo[i + (1<<(j-1))][j-1]);
sparse_minimo[i][j] = min (sparse_minimo[i][j-1], sparse_minimo[i + (1<<(j-1))][j-1]);
}
}
}
int maximizar (int a, int b)
{
int i = log2(b - a + 1);
return max (sparse_maximo[a][i], sparse_maximo[b - (1<<i) + 1][i]);
}
int minimizar (int a, int b)
{
int i = log2(b - a + 1);
return min (sparse_minimo[a][i], sparse_minimo[b - (1<<i) + 1][i]);
}
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)
{
if (N <= 3000 && (int)X.size() <= 6000 && (int)S.size() <= 3000)
{
int Q = S.size();
int M = X.size();
REP(i, 0, M)
{
graph[X[i]].pb (Y[i]);
graph[Y[i]].pb (X[i]);
}
vector<int> ans(Q, 0);
REP(i, 0, Q)
{
if (S[i] < L[i] || E[i] > R[i])
{
ans[i] = 0;
continue;
}
possiveis[0].push (S[i]);
dfs (S[i], i, 0, R[i], L[i]);
while (!possiveis[0].empty())
{
dfs (possiveis[0].front(), i, 1, R[i], L[i]);
if (possiveis[0].front() <= R[i] && possiveis[0].front() >= L[i])
possiveis[1].push (possiveis[0].front());
possiveis[0].pop();
if (visited[E[i]] > i)
{
ans[i] = 1;
while (!possiveis[0].empty())
possiveis[0].pop();
while (!possiveis[1].empty())
possiveis[1].pop();
break;
}
}
if (ans[i] != 0)
continue;
while (!possiveis[1].empty())
{
dfs (possiveis[1].front(), i, 2, R[i], L[i]);
possiveis[1].pop();
if (visited[E[i]] > i)
{
ans[i] = 1;
while (!possiveis[1].empty())
possiveis[1].pop();
break;
}
}
}
return ans;
}
int Q = S.size();
vector<int> ans(Q);
REP(i, 0, (int)X.size())
{
graph[X[i]].pb (Y[i]);
graph[Y[i]].pb (X[i]);
}
REP(i, 0, N)
{
if ((int)graph[i].size() == 1)
{
ordem[0] = i;
posicao[i] = 0;
break;
}
}
ordem[1] = graph[ordem[0]][0];
posicao[ordem[1]] = 1;
REP(i, 2, N)
{
if (graph[ordem[i-1]][0] == ordem[i-2])
ordem[i] = graph[ordem[i-1]][1];
else
ordem[i] = graph[ordem[i-1]][0];
posicao[ordem[i]] = i;
}
create(N);
REP(i, 0, Q)
{
int inicio = posicao[S[i]];
int fim = posicao[E[i]];
if (S[i] < L[i] || E[i] > R[i])
{
ans[i] = 0;
continue;
}
if (inicio < fim)
{
int minimo = inicio, maximo = fim;
while (minimo != maximo)
{
int med = (minimo + maximo + 1)/2;
if (minimizar(inicio, med) < L[i])
maximo = med - 1;
else
minimo = med;
}
if (maximizar(minimo, fim) > R[i])
ans[i] = 0;
else
ans[i] = 1;
}
else
{
int minimo = fim, maximo = inicio;
while (minimo != maximo)
{
int med = (minimo + maximo)/2;
if (minimizar(med, inicio) < L[i])
minimo = med + 1;
else
maximo = med;
}
if (maximizar(fim, minimo) > R[i])
ans[i] = 0;
else
ans[i] = 1;
}
}
return ans;
}
