#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define sz(a) (int)a.size()
template<typename T, bool zero_indexing>
struct fenwick_tree {
int N;
vector<T> fen;
fenwick_tree(int n) {
N = n, fen.assign(n + 1, 0);
}
fenwick_tree(vector<T> a) {
N = a.size();
fen.assign(N + 1, 0);
for(int i = 0; i < N; ++i) {
add(i, a[i]);
}
}
void add(int p, T val) {
for(int i = p + zero_indexing;i <= N;i += i & -i) {
fen[i] += val;
}
}
void set(int p, T val) {
T set_val = val - query(p, p);
add(p, set_val);
}
T query(int l, int r) {
T ret = 0;
for(int i = r + zero_indexing; i >= 1; i -= i & -i) {
ret += fen[i];
}
for(int i = l + zero_indexing - 1; i >= 1; i -= i & -i) {
ret -= fen[i];
}
return ret;
}
};
const int N = 2e5 + 10;
int d[N], s1[N], s2[N], in1[N], in2[N], f1 = 0, f2 = 0;
vector<int> g1[N], g2[N];
int get(int a) {
return d[a] = (d[a] == a ? a : get(d[a]));
}
void dfs1(int u) {
s1[u] = 1;
in1[u] = f1++;
for(int v: g1[u]) {
dfs1(v);
s1[u] += s1[v];
}
}
void dfs2(int u) {
s2[u] = 1;
in2[u] = f2++;
for(int v: g2[u]) {
dfs2(v);
s2[u] += s2[v];
}
}
struct query {
int l, r, idx;
};
const int S = 600;
bool cmp(query a, query b) {
pair<int, int> A = {a.l / S, a.r};
pair<int, int> B = {b.l / S, b.r};
return A < B;
}
vector<int> check_validity(int n, vector<int> x, vector<int> y, vector<int> s, vector<int> e, vector<int> l, vector<int> r) {
forn(i, N) d[i] = i;
int m = sz(x), q = sz(l);
vector<vector<int>> edges(n);
vector<int> root1(q), root2(q);
vector<int> ss[n + 5], ee[n + 5];
for(int i = 0;i < m; ++i) {
edges[x[i]].pb(y[i]);
edges[y[i]].pb(x[i]);
}
for(int i = 0;i < q; ++i) {
ss[l[i]].pb(i);
ee[r[i]].pb(i);
}
for(int i = n - 1; i >= 0; --i) {
set<int> st;
for(int v: edges[i]) {
if(v < i) continue;
st.insert(get(v));
}
for(auto x: st) {
g1[i].pb(x);
d[x] = i;
}
for(auto x: ss[i]) root1[x] = get(s[x]);
}
forn(i, N) d[i] = i;
for(int i = 0; i < n; ++i) {
set<int> st;
for(int v: edges[i]) {
if(v > i) continue;
st.insert(get(v));
}
for(auto x: st) {
g2[i].pb(x);
d[x] = i;
}
for(auto x: ee[i]) {
root2[x] = get(e[x]);
}
}
dfs1(0);
dfs2(n - 1);
for(int i = 0; i < n; ++i) {
assert(s1[i] > 0);
}
for(int i = n - 1; i >= 0; --i) {
assert(s2[i] > 0);
}
vector<query> qr;
for(int i = 0; i < q; ++i) {
qr.pb({in2[root2[i]], in2[root2[i]] + s2[root2[i]] - 1, i});
}
sort(all(qr), cmp);
vector<pair<int, int>> v;
for(int i = 0;i < n; ++i) {
v.pb({in2[i], i});
}
sort(all(v));
int L = 0, R = 0;
fenwick_tree<int, 1> st(n);
st.add(in1[v[L].second], 1);
vector<int> ans(q, 0);
for(auto Q: qr) {
while(R > Q.r) {
st.add(in1[v[R].second], -1);
--R;
}
while(L < Q.l) {
st.add(in1[v[L].second], -1);
++L;
}
while(L > Q.l) {
--L;
st.add(in1[v[L].second], 1);
}
while(R < Q.r) {
++R;
st.add(in1[v[R].second], 1);
}
int node = root1[Q.idx];
if(st.query(in1[node], in1[node] + s1[node] - 1) > 0) {
ans[Q.idx] = 1;
}
}
//forn(i, q) cout << ans[i] << "\n";
return ans;
}
/*
void solve() {
int n, m, q; cin >> n >> m >> q;
vector<int> x(m), y(m), s(q), e(q), l(q), r(q);
forn(i, m) cin >> x[i];
forn(i, m) cin >> y[i];
forn(i, q) cin >> s[i];
forn(i, q) cin >> e[i];
forn(i, q) cin >> l[i];
forn(i, q) cin >> r[i];
check_validity(n, x, y, s, e, l, r);
}
int32_t main() {
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int t = 1;
//cin >> t;
while(t--) {
solve();
}
}
/*
6 6 3
5 1 1 3 3 5
1 2 3 4 0 2
4 4 5
2 2 4
1 2 3
2 2 4
*/
