#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 10;
struct query
{
int l, r, s, e;
query(int _l = 0, int _r = 0, int _s = 0, int _e = 0)
{
l = _l;
r = _r;
s = _s;
e = _e;
}
} ask[maxn];
int n, q, m, used0[maxn], used1[maxn];
vector < int > graph[maxn];
void bfs0(int v, int l)
{
if (v < l)
return;
used0[v] = 1;
queue < int > q;
q.push(v);
while(!q.empty())
{
int cur = q.front();
q.pop();
for (int u : graph[cur])
{
if (u < l)
continue;
if (used0[u] == 0)
{
q.push(u);
used0[u] = 1;
}
}
}
}
void bfs1(int v, int r)
{
if (v > r)
return;
used1[v] = 1;
queue < int > q;
q.push(v);
while(!q.empty())
{
int cur = q.front();
q.pop();
for (int u : graph[cur])
{
if (u > r)
continue;
if (used1[u] == 0)
{
q.push(u);
used1[u] = 1;
}
}
}
}
int solve_query(query cur)
{
for (int i = 0; i < n; i ++)
{
used0[i] = used1[i] = 0;
}
bfs0(cur.s, cur.l);
bfs1(cur.e, cur.r);
for (int i = 0; i < n; i ++)
{
if (used0[i] == 1 && used1[i] == 1)
return 1;
}
return 0;
}
int chain[maxn], pos, chain_idx[maxn];
void make_chain(int v, int bef)
{
chain[++ pos] = v;
chain_idx[v] = pos;
for (int u : graph[v])
{
if (u == bef)
continue;
make_chain(u, v);
}
}
struct node
{
int max_num, min_num;
node(int _max_num = -1e9, int _min_num = 1e9)
{
max_num = _max_num;
min_num = _min_num;
}
};
node tree[4 * maxn];
void build_tree(int root, int left, int right)
{
if (left == right)
{
tree[root] = node(chain[left], chain[right]);
return;
}
int mid = (left + right) / 2;
build_tree(root * 2, left, mid);
build_tree(root * 2 + 1, mid + 1, right);
tree[root].max_num = max(tree[root * 2].max_num, tree[root * 2 + 1].max_num);
tree[root].min_num = min(tree[root * 2].min_num, tree[root * 2 + 1].min_num);
}
int rightmost_lower(int root, int left, int right,
int qleft, int qright, int val)
{
///cout << "here " << left << " " << right << " " << val << " " << tree[root].min_num << " " << qleft << " " << qright << endl;
if (left > qright || right < qleft ||
tree[root].min_num >= val)
return 0;
if (left == right)
return left;
int mid = (left + right) / 2;
if (left >= qleft && right <= qright)
{
if (tree[root * 2 + 1].min_num < val)
return rightmost_lower(root * 2 + 1, mid + 1, right, qleft, qright, val);
return rightmost_lower(root * 2, left, mid, qleft, qright, val);
}
return max(rightmost_lower(root * 2, left, mid, qleft, qright, val),
rightmost_lower(root * 2 + 1, mid + 1, right, qleft, qright, val));
}
int leftmost_lower(int root, int left, int right,
int qleft, int qright, int val)
{
///cout << "here " << left << " " << right << " " << val << " " << tree[root].min_num << " " << qleft << " " << qright << endl;
if (left > qright || right < qleft ||
tree[root].min_num >= val)
return n + 1;
if (left == right)
return left;
int mid = (left + right) / 2;
if (left >= qleft && right <= qright)
{
///cout << tree[root * 2].min_num << endl;
if (tree[root * 2].min_num < val)
return leftmost_lower(root * 2, left, mid, qleft, qright, val);
return leftmost_lower(root * 2 + 1, mid + 1, right, qleft, qright, val);
}
return min(leftmost_lower(root * 2, left, mid, qleft, qright, val),
leftmost_lower(root * 2 + 1, mid + 1, right, qleft, qright, val));
}
int rightmost_higher(int root, int left, int right,
int qleft, int qright, int val)
{
if (left > qright || right < qleft ||
tree[root].max_num <= val)
return 0;
if (left == right)
return left;
int mid = (left + right) / 2;
if (left >= qleft && right <= qright)
{
if (tree[root * 2 + 1].max_num > val)
return rightmost_higher(root * 2 + 1, mid + 1, right, qleft, qright, val);
return rightmost_higher(root * 2, left, mid, qleft, qright, val);
}
return max(rightmost_higher(root * 2, left, mid, qleft, qright, val),
rightmost_higher(root * 2 + 1, mid + 1, right, qleft, qright, val));
}
int leftmost_higher(int root, int left, int right,
int qleft, int qright, int val)
{
///cout << "here " << left << " " << right << " " << val << " " << tree[root].max_num << " " << qleft << " " << qright << endl;
if (left > qright || right < qleft ||
tree[root].max_num <= val)
return n + 1;
if (left == right)
return left;
int mid = (left + right) / 2;
if (left >= qleft && right <= qright)
{
///cout << tree[root * 2].max_num << endl;
if (tree[root * 2].max_num > val)
return leftmost_higher(root * 2, left, mid, qleft, qright, val);
return leftmost_higher(root * 2 + 1, mid + 1, right, qleft, qright, val);
}
return min(leftmost_higher(root * 2, left, mid, qleft, qright, val),
leftmost_higher(root * 2 + 1, mid + 1, right, qleft, qright, val));
}
int answer_line_query(query cur)
{
int lbs = rightmost_lower(1, 1, n, 1, chain_idx[cur.s], cur.l);
int rbs = leftmost_lower(1, 1, n, chain_idx[cur.s], n, cur.l);
int lbe = rightmost_higher(1, 1, n, 1, chain_idx[cur.e], cur.r);
int rbe = leftmost_higher(1, 1, n, chain_idx[cur.e], n, cur.r);
lbs ++;
rbs --;
lbe ++;
rbe --;
///cout << lbs << " : " << rbs << " " << lbe << " " << rbe <<endl;
if (lbs > lbe)
{
swap(lbs, lbe);
swap(rbs, rbe);
}
if (rbs >= lbe)
return 1;
return 0;
}
vector<int> check_validity(int N, vector<int> X, vector<int> Y,
vector<int> S, vector<int> E,
vector<int> L, vector<int> R)
{
n = N;
q = L.size();
m = X.size();
for (int i = 0; i < q; i ++)
{
ask[i] = query(L[i], R[i], S[i], E[i]);
}
for (int i = 0; i < m; i ++)
{
graph[X[i]].push_back(Y[i]);
graph[Y[i]].push_back(X[i]);
}
if (n <= 3000 && m <= 6000 && q <= 3000)
{
vector < int > ans(q, 0);
for (int i = 0; i < q; i ++)
{
ans[i] = solve_query(ask[i]);
}
return ans;
}
else
{
int beg = 1;
while(graph[beg].size() == 2)
beg ++;
make_chain(beg, -1);
build_tree(1, 1, n);
vector < int > ans(q);
/**for (int i = 1; i <= n; i ++)
{
cout << chain[i] << " ";
}
cout << endl;*/
for (int i = 0; i < q; i ++)
{
ans[i] = answer_line_query(ask[i]);
}
return ans;
}
}
