#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int n, m, q;
int X[maxn], Y[maxn], S[maxn], E[maxn], L[maxn], R[maxn];
vector <int> g[maxn];
vector <int> adj[maxn][2];
struct DisjointSet{
int par[maxn], root;
void init(){
for(int i = 1; i <= n; i++){
par[i] = i;
}
}
int find(int i){
return par[i] == i ? i : par[i] = find(par[i]);
}
bool joint(int u, int v, int t){
int x = find(u), y = find(v);
if(x == y) return 0;
adj[x][t].push_back(y);
root = x;
par[y] = x;
return 1;
}
} DSU0, DSU1;
int tin[maxn][2], tout[maxn][2], timedfs, jump[maxn][20][2], arr[maxn][2];
void dfs(int u, int t){
tin[u][t] = ++ timedfs;
arr[timedfs][t] = u;
for(int &v : adj[u][t]){
jump[v][0][t] = u;
for(int j = 1; (1 << j) <= n; j++){
jump[v][j][t] = jump[jump[v][j - 1][t]][j - 1][t];
}
dfs(v, t);
}
tout[u][t] = timedfs;
}
vector <array <int, 4>> ask[maxn];
int bit[maxn];
void up(int u, int val){
for(int i = u; i <= n; i+= i&-i) bit[i]+= val;
}
int get(int u){
int sum = 0;
for(int i = u; i; i-= i&-i) sum+= bit[i];
return sum;
}
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 = S.size();
m = X.size();
vector <int> ans(q, 0);
for(int i = 0; i < m; i++){
// cin >> X[i];
X[i]++;
}
for(int i = 0; i < m; i++){
// cin >> Y[i];
Y[i]++;
}
for(int i = 0; i < q; i++){
// cin >> S[i];
S[i]++;
}
for(int i = 0; i < q; i++){
// cin >> E[i];
E[i]++;
}
for(int i = 0; i < q; i++){
// cin >> L[i];
L[i]++;
}
for(int i = 0; i < q; i++){
// cin >> R[i];
R[i]++;
}
for(int i = 0; i < m; i++){
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
DSU0.init();
DSU1.init();
for(int i = 1; i <= n; i++){
for(int j : g[i]) if(j < i){
DSU0.joint(i, j, 0);
}
}
for(int i = n; i >= 1; i--){
for(int j : g[i] ) if(j > i){
DSU1.joint(i, j, 1);
}
}
timedfs = 0;
dfs(DSU0.root, 0);
timedfs = 0;
dfs(DSU1.root, 1);
for(int i = 0; i < q; i++){
int l = L[i], r = R[i], s = S[i], t = E[i];
int z = __lg(n);
for(int ss = z; ss >= 0; ss--){
if(jump[s][ss][1] >= l) s = jump[s][ss][1];
if(jump[t][ss][0] <= r && jump[t][ss][0] != 0) t = jump[t][ss][0];
}
ask[tout[t][0]].push_back({tin[s][1], tout[s][1], i, 1});
ask[tin[t][0] - 1].push_back({tin[s][1], tout[s][1], i, - 1});
}
for(int j = 1; j <= n; j++){
up(tin[arr[j][0]][1], 1);
for(auto it : ask[j]){
ans[it[2]]+= it[3] * (get(it[1]) - get(it[0] - 1));
}
}
for(int i = 0; i < q; i++){
ans[i] = (ans[i] > 0);
}
return ans;
}
// int32_t main(){
// ios_base::sync_with_stdio(0); cin.tie(0);
// #define koa "kieuoanh"
// if(fopen(koa".inp", "r")){
// freopen(koa".inp", "r", stdin); freopen(koa".out", "w", stdout);
// }
// cin >> n >> m >> q;
// for(int i = 1; i <= m; i++){
// cin >> X[i];
// X[i]++;
// }
// for(int i = 1; i <= m; i++){
// cin >> Y[i];
// Y[i]++;
// }
// for(int i = 1; i <= q; i++){
// cin >> S[i];
// S[i]++;
// }
// for(int i = 1; i <= q; i++){
// cin >> E[i];
// E[i]++;
// }
// for(int i = 1; i <= q; i++){
// cin >> L[i];
// L[i]++;
// }
// for(int i = 1; i <= q; i++){
// cin >> R[i];
// R[i]++;
// }
// for(int i = 1; i <= m; i++){
// g[X[i]].push_back(Y[i]);
// g[Y[i]].push_back(X[i]);
// }
// DSU0.init();
// DSU1.init();
// for(int i = 1; i <= n; i++){
// for(int j : g[i]) if(j < i){
// DSU0.joint(i, j, 0);
// }
// }
// for(int i = n; i >= 1; i--){
// for(int j : g[i] ) if(j > i){
// DSU1.joint(i, j, 1);
// }
// }
// timedfs = 0;
// dfs(DSU0.root, 0);
// timedfs = 0;
// dfs(DSU1.root, 1);
// for(int i = 1; i <= q; i++){
// int l = L[i], r = R[i], s = S[i], t = E[i];
// int z = __lg(n);
// for(int ss = z; ss >= 0; ss--){
// if(jump[s][ss][1] >= l) s = jump[s][ss][1];
// if(jump[t][ss][0] <= r && jump[t][ss][0] != 0) t = jump[t][ss][0];
// }
// ask[tout[t][0]].push_back({tin[s][1], tout[s][1], i, 1});
// ask[tin[t][0] - 1].push_back({tin[s][1], tout[s][1], i, - 1});
// }
// for(int j = 1; j <= n; j++){
// up(tin[arr[j][0]][1], 1);
// for(auto it : ask[j]){
// ans[it[2]]+= it[3] * (get(it[1]) - get(it[0] - 1));
// }
// }
// for(int i = 1; i <= q; i++){
// cout << (ans[i] > 0) << "\n";
// }
// return 0;
// }
