#include <bits/stdc++.h>
using namespace std;
struct UnionFind {
vector<int> parent_or_neg_size, edge_parity;
struct UndoInfo {
int i, i_pz, i_ep;
int j, j_pz, j_ep;
};
vector<UndoInfo> undo_info;
UnionFind(int n) : parent_or_neg_size(n, -1),
edge_parity(n, 0) {}
pair<int, int> find_root_and_parity(int i) {
int parity = 0;
while (parent_or_neg_size[i] >= 0) {
parity ^= edge_parity[i];
i = parent_or_neg_size[i];
}
return {i, parity};
}
enum UniteResult { NO_CYCLE, EVEN_CYCLE, ODD_CYCLE };
UniteResult unite(int i, int j, bool new_edge_parity = true, bool save_undo_info = false) {
auto [root_i, parity_i] = find_root_and_parity(i);
auto [root_j, parity_j] = find_root_and_parity(j);
if (root_i == root_j) {
if (save_undo_info) {
undo_info.push_back({0, 0, 0, 0, 0, 0});
}
if (parity_i ^ parity_j ^ new_edge_parity) {
return ODD_CYCLE;
} else {
return EVEN_CYCLE;
}
}
if (parent_or_neg_size[root_i] > parent_or_neg_size[root_j]) {
swap(root_i, root_j);
swap(parity_i, parity_j);
}
if (save_undo_info) {
undo_info.push_back({
.i = root_i,
.i_pz = parent_or_neg_size[root_i],
.i_ep = edge_parity[root_i],
.j = root_j,
.j_pz = parent_or_neg_size[root_j],
.j_ep = edge_parity[root_j],
});
}
parent_or_neg_size[root_i] += parent_or_neg_size[root_j];
parent_or_neg_size[root_j] = root_i;
edge_parity[root_j] = parity_i ^ parity_j ^ new_edge_parity;
return NO_CYCLE;
}
void undo() {
assert(!undo_info.empty());
auto [i, i_pz, i_ep, j, j_pz, j_ep] = undo_info.back();
undo_info.pop_back();
if (i == 0 && j == 0) {
return;
}
parent_or_neg_size[i] = i_pz;
edge_parity[i] = i_ep;
parent_or_neg_size[j] = j_pz;
edge_parity[j] = j_ep;
}
void undo_all() {
while (!undo_info.empty()) {
undo();
}
}
};
int main() {
int n, m, q;
cin >> n >> m >> q;
vector<array<int, 2>> edges(m);
for (auto &[u, v] : edges) {
cin >> u >> v;
--u;
--v;
}
static constexpr auto BLOCK_SIZE = 400;
std::vector<array<int, 2>> queries(q);
std::vector<std::basic_string<int>> blocks((m + BLOCK_SIZE - 1) / BLOCK_SIZE);
std::vector<bool> answers(q);
for (int qq = 0; qq != q; ++qq) {
auto &[l, r] = queries[qq];
cin >> l >> r;
--l;
blocks[l / BLOCK_SIZE].push_back(qq);
}
UnionFind uf(n);
for (int lid = 0; lid != int(blocks.size()); ++lid) {
uf.parent_or_neg_size.assign(n, -1);
std::sort(blocks[lid].begin(), blocks[lid].end(), [&](int i, int j) {
auto &[l0, r0] = queries[i];
auto &[l1, r1] = queries[j];
return r0 > r1;
});
int min_l = lid * BLOCK_SIZE;
bool base_has_odd_cycle = false;
for (int j = 0; j != min_l; ++j) {
auto [u, v] = edges[j];
if (uf.unite(u, v) == UnionFind::ODD_CYCLE) {
base_has_odd_cycle = true;
break;
}
}
int last_added = m;
for (int qq : blocks[lid]) {
auto &[l, r] = queries[qq];
while (!base_has_odd_cycle && r < last_added) {
auto [u, v] = edges[--last_added];
if (uf.unite(u, v) == UnionFind::ODD_CYCLE) {
base_has_odd_cycle = true;
}
}
bool has_odd_cycle = base_has_odd_cycle;
for (int j = min_l; !has_odd_cycle && j != l; ++j) {
auto [u, v] = edges[j];
if (uf.unite(u, v, true, true) == UnionFind::ODD_CYCLE) {
has_odd_cycle = true;
}
}
answers[qq] = has_odd_cycle;
uf.undo_all();
}
}
for (bool answer : answers) {
cout << (answer ? "YES" : "NO") << '\n';
}
}
