// M
#include<bits/stdc++.h>
#include "werewolf.h"
#define pb push_back
using namespace std;
const int N = 400005;
int n, m, q, P[N], la[N], ra[N], lb[N], rb[N];
pair < int , int > targ[N];
vector < int > Adj[N], A[N], Event[N];
vector < pair < int , int > > Qvent[N];
int Find(int v)
{
return (P[v] < 0 ? v : (P[v] = Find(P[v])));
}
inline void Merge(int v, int u)
{
v = Find(v);
u = Find(u);
if (v == u)
return ;
if (P[v] > P[u])
swap(v, u);
for (int a : A[u])
A[v].pb(a);
A[u].clear();
P[v] += P[u];
P[u] = v;
}
inline void Init()
{
memset(P, -1, sizeof(P));
for (int i = 0; i < n; i ++)
A[i].clear(), A[i].pb(i), Event[i].clear();
}
vector < int > check_validity(int _n, vector < int > _U, vector < int > _V, vector < int > S, vector < int > E, vector < int > L, vector < int > R)
{
n = _n;
m = (int)_U.size();
q = (int)S.size();
for (int i = 0; i < m; i ++)
{
Adj[_U[i]].push_back(_V[i]);
Adj[_V[i]].push_back(_U[i]);
}
Init();
for (int i = 0; i < q; i ++)
Event[R[i]].pb(i);
for (int i = 0; i < n; i ++)
{
for (int u : Adj[i])
if (u < i)
Merge(u, i);
for (int e : Event[i])
targ[e] = make_pair(Find(E[e]), A[Find(E[e])].size());
}
vector < int > vec;
for (int i = 0; i < n; i ++)
if (Find(i) == i)
vec = A[i];
assert(vec.size() == n);
vector < int > rev(n);
for (int i = 0; i < n; i ++)
rev[vec[i]] = i;
for (int i = 0; i < q; i ++)
la[i] = rev[targ[i].first], ra[i] = la[i] + targ[i].second;
Init();
for (int i = 0; i < q; i ++)
Event[L[i]].pb(i);
for (int i = n - 1; i >= 0; i --)
{
for (int u : Adj[i])
if (u > i)
Merge(u, i);
for (int e : Event[i])
targ[e] = make_pair(Find(S[e]), A[Find(S[e])].size());
}
vector < int > dec;
for (int i = 0; i < n; i ++)
if (Find(i) == i)
dec = A[i];
assert(dec.size() == n);
for (int i = 0; i < n; i ++)
rev[dec[i]] = i;
for (int i = 0; i < q; i ++)
lb[i] = rev[targ[i].first], rb[i] = lb[i] + targ[i].second;
for (int i = 0; i < n; i ++)
rev[vec[i]] = i;
for (int i = 0; i < n; i ++)
dec[i] = rev[dec[i]];
for (int i = 0; i < q; i ++)
{
if (rb[i])
Qvent[rb[i] - 1].pb({i, 1});
if (lb[i])
Qvent[lb[i] - 1].pb({i, -1});
}
vector < int > F(N, 0);
auto AddFen = [&](int i, int val){
for (i ++; i < N; i += i & - i)
F[i] += val;
};
auto GetFen = [&](int i){
int rt = 0;
for (i ++; i; i -= i & - i)
rt += F[i];
return rt;
};
auto GetFenLR = [&](int l, int r){
return GetFen(r - 1) - GetFen(l - 1);
};
vector < int > Rs(q, 0);
for (int i = 0; i < n; i ++)
{
AddFen(dec[i], 1);
for (auto e : Qvent[i])
{
int qid = e.first;
Rs[qid] += GetFenLR(la[qid], ra[qid]) * e.second;
}
}
for (int i = 0; i < q; i ++)
if (Rs[i]) Rs[i] = 1;
return Rs;
}
