#include "werewolf.h"
#include <bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N = 2e5 + 69;
/*
g++ werewolf.cpp werewolf.h grader.cpp
./a.out
*/
int p[N], sz[N];
vector<pair<int, int>> t[N];
vector<pair<int, int>> qs[N];
vector<int> g[N];
int root(int v) {
if (p[v] == v)
return v;
return p[v] = root(p[v]);
}
vector<int> check_validity(int n, vector<int> u, vector<int> v, vector<int> s, vector<int> e, vector<int> l, vector<int> r) {
int q = s.size();
int m = u.size();
vector<int> ans(q);
vector<tuple<int, int, int>> edges;
for (int i = 0;i < m;i++) {
++u[i], ++v[i];
g[u[i]].push_back(v[i]);
g[v[i]].push_back(u[i]);
}
for (int i = 0;i < q;i++) {
l[i]++, r[i]++;
s[i]++, e[i]++;
}
for (int i = 1;i <= n;i++) {
p[i] = i;
sz[i] = 1;
}
for (int i = 0;i < q;i++)
qs[l[i]].push_back({r[i], i});
for (int i = 0;i < m;i++) {
int a = u[i], b = v[i];
int c = min(a, b);
edges.push_back({c, a, b});
}
sort(edges.begin(), edges.end());
int ptr = m - 1;
for (int i = n;i >= 1;i--) {
while (ptr >= 0 && get<0>(edges[ptr]) >= i) {
int a = get<1>(edges[ptr]), b = get<2>(edges[ptr]);
ptr--;
int x = root(a), y = root(b);
if (x != y) {
if (sz[x] < sz[y])
swap(x, y);
sz[x] += sz[y];
p[y] = x;
}
}
for (auto j : qs[i]) {
int r = j.f, ind = j.s;
queue<int> q;
vector<int> vis(n + 1);
for (int k = 1;k <= n;k++) {
if (root(k) == root(s[ind]) && k >= i && k <= r) {
q.push(k);
}
}
while (!q.empty()) {
auto v = q.front();
q.pop();
vis[v] = 1;
for (auto u : g[v]) {
if (vis[u] || u > r)
continue;
vis[u] = 1;
q.push(u);
}
}
ans[ind] = vis[e[ind]];
}
}
return ans;
}
/*
6 6 3
5 1
1 2
2 5
1 3
3 4
0 3
4 2 1 2
4 2 2 2
5 4 3 4
*/
