#include "werewolf.h"
#include <bits/stdc++.h>
#include <random>
#include <chrono>
#include <array>
using namespace std;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define prev prev123
#define pii pair<int, int>
#define fr first
#define sc second
typedef vector<int> vi;
const int MAXN = (int)2e5 + 5;
const int MAXM = (int)4e5 + 5;
const int MAXQ = (int)2e5 + 5;
vector <int> g[MAXN];
int N, M, Q;
struct Query {
int s, e, l, r;
Query (int s_, int e_, int l_, int r_) {
s = s_, e = e_, l = l_, r = r_;
}
Query () {
}
}query[MAXQ];
struct Small_Solve {
vector <int> ans;
bool need() {
return (N <= 3000 && M <= 6000 && Q <= 3000);
}
void solve() {
ans.resize(Q, 0);
vector <int> used[3];
used[1].resize(N, 0);
used[2].resize(N, 0);
int cnt = 0;
for (int i = 0; i < Q; i++) {
cnt++;
queue <int> q[3];
if (query[i].s >= query[i].l) {
q[1].push(query[i].s);
}
if (query[i].e <= query[i].r) {
q[2].push(query[i].e);
}
while (!q[1].empty()) {
int v = q[1].front();
q[1].pop();
if (used[1][v] == cnt) {
continue;
}
used[1][v] = cnt;
for (int to : g[v]) {
if (to >= query[i].l) {
q[1].push(to);
}
}
}
while (!q[2].empty()) {
int v = q[2].front();
q[2].pop();
if (used[2][v] == cnt) {
continue;
}
used[2][v] = cnt;
for (int to : g[v]) {
if (to <= query[i].r) {
q[2].push(to);
}
}
}
int found = 0;
for (int v = 0; v < N; v++) {
found |= (used[1][v] == cnt && used[2][v] == cnt);
}
ans[i] = found;
}
}
}subtask12;
struct Line_Solve {
int start = -1, finish = -1;
pii table[20][(int)2e5 + 5];
int pows[20];
vector <bool> used;
vector <int> pos;
vector <int> convert;
vector <int> ans;
Line_Solve() {
pows[0] = 1;
for (int i = 0; i < 20; i++) {
pows[i] = pows[i - 1] * 2;
}
}
bool need() {
if (M != N - 1) {
return false;
}
for (int i = 0; i < N; i++) {
if (szof(g[i]) == 1) {
if (start == -1) {
start = i;
} else {
finish = i;
}
}
}
return true;
}
pii merge(pii &a, pii &b) {
return {min(a.fr, b.fr), max(a.sc, b.sc)};
}
bool in(int l1, int r1, int l2, int r2) { // l1...r1 in l2...r2
return (l2 <= l1 && r1 <= r2);
}
pii get(int l, int r) {
if (l == r) {
return table[0][l];
} else {
int pw = log2(r - l + 1);
return merge(table[pw][l], table[pw][r - pows[pw] + 1]);
}
};
pii get_segment(int our_pos, int L, int R) {
pii segment = {-1, -1};
int l = -1, r = our_pos;
while (r - l > 1) {
int mid = (l + r) >> 1;
pii pr = get(mid, our_pos);
if (in(pr.fr, pr.sc, L, R)) {
r = mid;
} else {
l = mid;
}
}
segment.fr = r;
l = our_pos, r = N;
while (r - l > 1) {
int mid = (l + r) >> 1;
pii pr = get(our_pos, mid);
if (in(pr.fr, pr.sc, L, R)) {
l = mid;
} else {
r = mid;
}
}
segment.sc = l;
return segment;
}
void dfs(int v, int id) {
used[v] = 1;
pos[v] = id;
convert[id] = v;
for (int to : g[v]) {
if (!used[to]) {
dfs(to, id + 1);
}
}
}
void solve() {
used.resize(N, false);
pos.resize(N);
convert.resize(N);
ans.resize(Q);
dfs(start, 0);
for (int pw = 0; pw < 20; pw++) {
for (int i = 0; i < N; i++) {
if (pw == 0) {
table[pw][i] = {convert[i], convert[i]};
} else if (i + pows[i] - 1 < N) {
table[pw][i] = merge(table[pw - 1][i], table[pw - 1][i + pows[pw - 1]]);
}
}
}
for (int i = 0; i < Q; i++) {
if ((query[i].s >= query[i].l && query[i].e <= query[i].r) == false) {
ans[i] = 0;
continue;
}
pii segment[3];
segment[1] = get_segment(query[i].s, query[i].l, N - 1);
segment[2] = get_segment(query[i].e, 0, query[i].r);
ans[i] = !(segment[1].fr > segment[2].sc || segment[2].fr > segment[1].sc);
}
}
}subtask3;
vi check_validity(int NN, vi X, vi Y, vi S, vi E, vi L, vi R) {
N = NN;
M = szof(X);
Q = szof(S);
for (int i = 0; i < NN; i++) {
g[i].clear();
}
for (int i = 0; i < M; i++) {
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
for (int i = 0; i < Q; i++) {
query[i] = Query(S[i], E[i], L[i], R[i]);
}
if (subtask3.need()) {
subtask3.solve();
return subtask3.ans;
} else {
return {};
}
}
//int gen(int l, int r) {
//long long int x = rnd();
//x = abs(x);
//return l + (x % (r - l + 1));
//}
//int pr[1000];
//int findp(int v);
//void unite(int u, int v);
//void not_line();
//signed main() {
//while (1) {
//int n = gen(2, 6);
//vector <int> vec;
//for (int i = 0; i < n; i++) {
//vec.push_back(i);
//}
//shuffle(vec.begin(), vec.end(), rnd);
//int NN, QQ;
//NN = n, QQ = gen(1, 5);
//vector <int> X(n - 1), Y(n - 1), S(QQ), E(QQ), L(QQ), R(QQ);
//for (int i = 0; i < n; i++) {
//if (i + 1 < n) {
//X[i] = vec[i];
//Y[i] = vec[i + 1];
//}
//}
//for (int i = 0; i < QQ; i++) {
//do {
//S[i] = gen(0, NN - 1), E[i] = gen(0, NN - 1);
//}
//while (S[i] == E[i]);
//L[i] = gen(0, NN - 1);
//R[i] = gen(0, NN - 1);
//}
//vector <int> ans = check_validity(NN, X, Y, S, E, L, R);
//}
//}
///////////////////////////////////////////////
//int findp(int v) {
//if (v == pr[v]) {
//return v;
//}
//return pr[v] = findp(pr[v]);
//}
//void unite(int x, int y) {
//x = findp(x);
//y = findp(y);
//if (x == y) {
//return;
//}
//pr[x] = y;
//}
//void not_line() {
//while (1) {
//vector <vector<int>> put;
//int NN = gen(1, 5);
//int MM = gen(NN - 1, NN * (NN - 1) / 2);
//int QQ = gen(1, 1);
//vector<int> X(MM), Y(MM), S(QQ), E(QQ), L(QQ), R(QQ);
//for (int i = 0; i < NN; i++) {
//pr[i] = i;
//}
//set <pii> edges;
//int xod = 0;
//int cnt = 0;
//while (cnt < NN - 1) {
//int x = -1, y = -1;
//while (x == y || findp(x) == findp(y)) {
//x = gen(0, NN - 1);
//y = gen(0, NN - 1);
//}
//unite(x, y);
//X[xod] = x, Y[xod] = y;
//edges.insert({x, y});
//edges.insert({y, x});
//xod++;
//cnt++;
//put.push_back({x, y});
//}
//for (int i = NN; i <= MM; i++) {
//int x = -1, y = -1;
//while (x == y || edges.find({x, y}) != edges.end() || edges.find({y, x}) != edges.end()) {
//x = gen(0, NN - 1);
//y = gen(0, NN - 1);
//}
//X[xod] = x;
//Y[xod] = y;
//edges.insert({x, y});
//edges.insert({y, x});
//put.push_back({x, y});
//}
//for (int i = 0; i < QQ; ++i) {
//S[i] = gen(0, NN - 1);
//do {
//E[i] = gen(0, NN - 1);
//} while (E[i] == S[i]);
//L[i] = gen(0, NN - 1);
//R[i] = gen(0, NN - 1);
//put.push_back({S[i], E[i], L[i], R[i]});
//}
//vector<int> A = check_validity(NN, X, Y, S, E, L, R);
//puts("finish");
//}
//}
/*
4
0 2
2 1
1 3
*/
/*
5 4 1
2 0
0 4
4 1
1 3
0 1 0 4
*/
