#include<bits/stdc++.h>
using namespace std;
#define int int64_t
#define i32 signed
#define X first
#define Y second
#define pb push_back
using pii = pair<int,int>;
#define vt vector
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define f0r(i,a,b) for(auto i = (a); i != (b); i++)
#define r0f(i,a,b) for(auto i = (a); i >= (b); i--)
#define debug(x) {auto _x=x;cerr<<#x<<": "<<_x<<'\n';};
const int INF = 1e9;
// r+1
// online bipartite dsu
// par[x] = find(par[x])
// vt<int> cc
// merge by size
// walk from the back
// yes[r+1] if the graph is bipartite
//edge case if r = N just say yes
int n,m,q;
vt<pii> edges;
//Yes, n is the number of nodes, correct.
struct merge_op {
bool before_odd_cycle;
int u,v;
vt<int> ccu;
merge_op() {}
merge_op(int u, int v, vt<int> ccu, bool before): u(u), v(v), ccu(ccu), before_odd_cycle(before) {}
};
struct Dsu { //ALways on the NOdes
vt<vt<int>> component_nodes;
vt<int> parent;
vt<int> colours; //everything is colour 0 at the start
vt<merge_op> hist;
bool yes_odd_cycle = 0;
int ops = 0;
int find(int x) {
if(parent[x] == x) return x;
return find(parent[x]); //no path compression
}
void init() {
component_nodes.resize(n+5);
parent.resize(n+5);
colours.resize(n+5);
f0r(i,1,n+1) {
parent[i] = i;
component_nodes[i].pb(i);
}
}
void go_back_one_operation() {
assert(sz(hist));
merge_op cur_op = hist.back();
hist.pop_back();
int u = cur_op.u, v = cur_op.v;
bool before = cur_op.before_odd_cycle;
if(u != v) {
vt<int> ccu = cur_op.ccu;
parent[u] = u;
f0r(g,0,sz(ccu)) {
component_nodes[v].pop_back();
component_nodes[u].pb(ccu[g]);
}
yes_odd_cycle = before;
} else { //we just reset the before
yes_odd_cycle = before;
}
} //validity of colours should be maintained anyways...
void rollback(int save_point) { //I think the rollback code is correct, we might be missing something though
while(ops > save_point) {
go_back_one_operation();
ops--;
}
}
int save() {
return ops;
}
void merge(int original_u, int original_v) { //Transfer component nodes and stuff
ops++;
int u_host = find(original_u), v_host = find(original_v);
if(u_host == v_host) {
bool before =yes_odd_cycle;
if(colours[original_u] == colours[original_v]) { //Yeah buddy this is NOT possible
yes_odd_cycle = 1;
} else { //Ignore this edge
}
hist.pb(merge_op(u_host, u_host, {}, before));
//BUG: forgot to return
return;
}
if(sz(component_nodes[u_host]) > sz(component_nodes[v_host])) {
swap(u_host, v_host);
}
hist.pb({u_host, v_host, component_nodes[u_host], yes_odd_cycle});
parent[u_host] = v_host; //Always need the smaller one
if(colours[original_u] == colours[original_v]) {
for(int node : component_nodes[u_host]) {
colours[node] = !colours[node];
}
}
for(int node : component_nodes[u_host]) {
component_nodes[v_host].pb(node);
}
component_nodes[u_host].clear();
}
} dsu; //dsu should have nothing to do with our edge array
//DNC find lastl by recursing, then rollbacking (but don't rollback the prefix)
vt<int> last;
void dnc(int need_l, int need_r, int optl, int optr) {
if(need_l > need_r) return;
//opt is the splitting point
//BUG: I think we should not be directly modifying optl
int mid = (need_l + need_r)/2;
//BUG:
int optm = INF, before_all_this = dsu.save();
for(int e = max(optl, mid); e <= optr; e++) { //assuming [1, need_l) is all filled, answer is definitely in this range
//makes sure to roll back to [1, need_l]
dsu.merge(edges[e].X, edges[e].Y);
if(dsu.yes_odd_cycle) {
optm = e;
break;
}
}
bool ret = dsu.yes_odd_cycle;
if(ret) last[mid] = optm; else last[mid] = INF;
dsu.rollback(before_all_this);
if(need_l == need_r) return;
//it's not n^2 btw
int before_any_recursion = dsu.save();
if(not ret) { //
dnc(need_l, mid-1, optl, optr);
for(int i = mid+1; i <= need_r; i++) {
last[i] = INF;
}
} else {
dnc(need_l, mid-1, optl, optm);
for(int e = optl; e < optm; e++) {
dsu.merge(edges[e].X, edges[e].Y);
}
dnc(mid+1, need_r, optm, optr);
}
dsu.rollback(before_any_recursion);
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n>>m>>q;
dsu.init();
// vt<int> suff (m+5); //Is each suffix of edges starting from i going to have an odd cycle?
edges = vt<pii> (2*m+5);
//BUG: these should have been m instead of n
f0r(i,1,m+1) { //for i from 1 to n, input the edges
int u,v; cin>>u>>v;
edges[i] = {u,v};
}
f0r(i,m+1, 2*m+1) { //copy over the edges
edges[i] = edges[i-m];
}
// debug("here i am");
last.resize(2*m+5); //for the start of each edge....
dnc(1, 2*m, 1, 2*m);
//f0r(i,1,2*m+1) { debug((i-1)%m + 1) debug(last[i]); }
f0r(g,0,q) {
int l,r;cin >>l>>r;
int v = last[r+1];
if(v != INF and v-m <= l) {
cout << "YES\n";
} else {
cout << "NO\n";
}
}
//Last array should be filled
// r0f(i,m,1) {
// dsu.merge(edges[i].X, edges[i].Y);
// suff[i] = dsu.yes_odd_cycle;
// }
// f0r(g,0,q) {
// int l,r;cin>>l>>r;
// //BUG: you still need to check if this is m because m is the limit of r
// if(r < m and suff[r+1]) {
// cout << "YES\n";
// } else {
// cout << "NO\n";
// }
// }
}
