#include "werewolf.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int maxn = 2e5 + 12;

vector<int> g[maxn];
bool used[maxn];
int pos[maxn], val[maxn];
int mx[22][maxn], mn[22][maxn];
int lg[maxn];
vector<int> ord;
int n, m, q;

void dfs(int v) {
    used[v] = true;
    pos[v] = (int)ord.size();
    val[(int)ord.size()] = v;
    ord.push_back(v);
    for(int to : g[v]) {
        if(!used[to]) {
            dfs(to);
        }
    }
}

int getmn(int l, int r) {
    int k = lg[r - l + 1];
    return min(mn[k][l], mn[k][r - (1 << k) + 1]);
}

int getmx(int l, int r) {
    int k = lg[r - l + 1];
    return max(mx[k][l], mx[k][r - (1 << k) + 1]);
}

vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> s, vector<int> t,
                                vector<int> l, vector<int> r) {
    n = N, m = (int)X.size(), q = (int)l.size();

    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 < n; i++) {
        if((int)g[i].size() == 1) {
            dfs(i);
            break;
        }
    }
    for(int i = 2; i <= n; i++) {
        lg[i] = lg[i / 2] + 1;
    }
    for(int i = 0; i < n; i++) {
        mx[0][i] = mn[0][i] = val[i];
    }
    for(int k = 1; k < 20; k++) {
        for(int i = 0; i + (1 << k) - 1 < n; i++) {
            mx[k][i] = max(mx[k - 1][i], mx[k - 1][i + (1 << (k - 1))]);
            mn[k][i] = min(mn[k - 1][i], mn[k - 1][i + (1 << (k - 1))]);
        }
    }
    vector<int> ans;

    for(int i = 0; i < q; i++) {
        s[i] = pos[s[i]], t[i] = pos[t[i]];
        if(s[i] < t[i]) {
            int L = s[i], R = t[i];
            for(int tl = s[i], tr = t[i]; tl <= tr;) {
                int mid = (tl + tr) >> 1;
                if(getmn(s[i], mid) >= l[i]) {
                    L = mid;
                    tl = mid + 1;
                }
                else tr = mid - 1;
            }
            for(int tl = s[i], tr = t[i]; tl <= tr;) {
                int mid = (tl + tr) >> 1;
                if(getmx(mid, t[i]) <= r[i]) {
                    R = mid;
                    tr = mid - 1;
                }
                else tl = mid + 1;
            }
            ans.push_back(R <= L);
        }

        else {
            int L = t[i], R = s[i];
            for(int tl = t[i], tr = s[i]; tl <= tr;) {
                int mid = (tl + tr) >> 1;
                if(getmn(mid, s[i]) >= l[i]) {
                    R = mid;
                    tr = mid - 1;
                }
                else tl = mid + 1;
            }
            for(int tl = t[i], tr = s[i]; tl <= tr;) {
                int mid = (tl + tr) >> 1;
                if(getmx(t[i], mid) <= r[i]) {
                    L = mid;
                    tl = mid + 1;
                }
                else tr = mid - 1;
            }
            ans.push_back(R <= L);
        }
    }
    return ans;
}