#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
class RangedTree {
public:
vector<int> dat[22], U; int ty, size_;
void init(int N, vector<int>T, int typ) {
size_ = N;
for (int i = 0; i < 22; i++) dat[i].resize(N + 2, 0);
for (int i = 0; i < N; i++) dat[0][i] = T[i];
for (int i = 0; i < 21; i++) {
for (int j = 0; j < N; j++) {
if (j + (1 << i) >= N) dat[i + 1][j] = dat[i][j];
else {
if (typ == 1) dat[i + 1][j] = min(dat[i][j], dat[i][j + (1 << i)]);
if (typ == 2) dat[i + 1][j] = max(dat[i][j], dat[i][j + (1 << i)]);
}
}
}
ty = typ;
U.resize(N + 2, 0);
for (int i = 0; i < 21; i++) {
for (int j = (1 << i); j < (2 << i); j++) {
if (j < (int)U.size()) U[j] = i;
}
}
}
int query(int cl, int cr) {
cr++; if (cr > size_) cr = size_;
int lens = cr - cl;
if (ty == 1) return min(dat[U[lens]][cl], dat[U[lens]][cr - (1 << U[lens])]);
if (ty == 2) return max(dat[U[lens]][cl], dat[U[lens]][cr - (1 << U[lens])]);
return -1;
}
};
int N, M, Q, dp[5009][2], I[200009], J[200009], Order[200009]; vector<int>G[200009];
RangedTree Z[2]; bool used[200009];
pair<int, int> calc(int ty, int pos, int lim) {
if (ty == 1) {
int L1 = 0, R1 = pos + 1, M1, T1 = pos;
for (int i = 0; i < 20; i++) {
M1 = (L1 + R1) / 2;
int B = Z[0].query(M1, pos);
if (B >= lim) { R1 = M1; T1 = min(T1, M1); }
else { L1 = M1; }
}
int L2 = pos, R2 = N, M2, T2 = pos;
for (int i = 0; i < 20; i++) {
M2 = (L2 + R2) / 2;
int B = Z[0].query(pos, M2);
if (B >= lim) { L2 = M2; T2 = max(T2, M2); }
else { R2 = M2; }
}
return make_pair(T1, T2);
}
if (ty == 2) {
int L1 = 0, R1 = pos + 1, M1, T1 = pos;
for (int i = 0; i < 20; i++) {
M1 = (L1 + R1) / 2;
int B = Z[1].query(M1, pos); //cout << "max [" << M1 << ", " << pos << "] = " << B << endl;
if (B <= lim) { R1 = M1; T1 = min(T1, M1); }
else { L1 = M1; }
}
int L2 = pos, R2 = N, M2, T2 = pos;
for (int i = 0; i < 20; i++) {
M2 = (L2 + R2) / 2;
int B = Z[1].query(pos, M2); //cout << "max [" << pos << ", " << M2 << "] = " << B << endl;
if (B <= lim) { L2 = M2; T2 = max(T2, M2); }
else { R2 = M2; }
}
return make_pair(T1, T2);
}
}
vector<int> check_validity(int NN, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
N = NN; 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]); }
if (!(N <= 3000 && M <= 6000 && Q <= 3000)){
// For subtask 3
int cx = -1; for (int i = 0; i < N; i++) { if (G[i].size() == 1) cx = i; }
int cntv = 0; used[cx] = true; I[cntv] = cx; cntv++;
while (true) {
int cp = -1; for (int i = 0; i < G[cx].size(); i++) { if (used[G[cx][i]]==false) cp=G[cx][i]; }
if (cp == -1) break;
I[cntv] = cp; cx = cp; cntv++; used[cx]=true;
}
vector<int> V; for (int i = 0; i < cntv; i++) { V.push_back(I[i]); Order[I[i]] = i; }
Z[0].init(N, V, 1);
Z[1].init(N, V, 2);
vector<int>ans;
for (int i = 0; i < Q; i++) {
//cout << "Start = " << Order[S[i]] << ", Goal = " << Order[E[i]] << endl;
pair<int, int> A1 = calc(1, Order[S[i]], L[i]);
pair<int, int> A2 = calc(2, Order[E[i]], R[i]);
pair<int, int> A3 = make_pair(max(A1.first, A2.first), min(A1.second, A2.second));
//cout << "Human = [" << A1.first << ", " << A1.second << "] , Wolf = [" << A2.first << ", " << A2.second << "]" << endl;
if (A3.first <= A3.second) ans.push_back(1);
else ans.push_back(0);
}
return ans;
}
else {
// For subtask 1, 2
vector<int>ans;
for (int i = 0; i < Q; i++) {
for (int j = 0; j <= N; j++) { dp[j][0] = 0; dp[j][1] = 0; }
dp[S[i]][0] = 1; queue<pair<int, int>> que; que.push(make_pair(S[i], 0));
while(!que.empty()){
int pos1 = que.front().first, pos2 = que.front().second; que.pop();
if (pos2 == 0 && dp[pos1][1] == 0 && L[i] <= pos1 && pos1 <= R[i]) {
dp[pos1][1] = 1;
que.push(make_pair(pos1, 1));
}
for (int j = 0; j < G[pos1].size(); j++) {
int to = G[pos1][j];
if (pos2 == 0 && to < L[i]) continue;
if (pos2 == 1 && R[i] < to) continue;
if (dp[to][pos2] == 1) continue;
dp[to][pos2] = 1;
que.push(make_pair(to, pos2));
}
}
ans.push_back(dp[E[i]][1]);
}
return ans;
}
}
