Odd Cycle in Gotham

The infamous Joker has returned to Gotham City with a devious plan. Gotham has \(N\) intersections (numbered from \(1\) to \(N\)) and \(M\) roads (numbered from \(1\) to \(M\)). Each road connects two different intersections, and there is at most one road between any pair of intersections.

To execute his plan, the Joker needs to traverse an odd cycle in the city. Formally, an odd cycle is a sequence \[ S, s_1, s_2, \ldots, s_k, S \] where \(k\) is even (so that the number of edges, \(k+1\), is odd) and there is a direct road between \(S\) and \(s_1\), between \(s_{i-1}\) and \(s_i\) for all \(2 \le i \le k\), and between \(s_k\) and \(S\).

However, the police have taken control of some of the roads. On the \(i\)-th day, the police control all roads with indices in the range \([l_i, r_i]\), so the Joker cannot use those roads. Having obtained the police schedule for the next \(Q\) days, the Joker now wants to know on which days his wicked plan can be executed, i.e. when there exists an odd cycle in the remaining network of roads.

Your task is to answer this query for each day. Note that when no road is controlled (i.e. the controlled range does not intersect with \([1, M]\)), the entire road network is available.

inputFormat

The first line contains three integers \(N\), \(M\), and \(Q\) \((1 \leq N, M, Q \leq \text{limit})\).

Each of the next \(M\) lines contains two integers \(u\) and \(v\) representing a road connecting intersections \(u\) and \(v\). The roads are numbered from \(1\) to \(M\) in the given order.

Each of the next \(Q\) lines contains two integers \(l_i\) and \(r_i\) indicating that on the \(i\)-th day, the police control all roads with indices in the range \([l_i, r_i]\). If the range \([l_i, r_i]\) does not intersect with \([1, M]\), it means no road is controlled that day.

outputFormat

For each query (day), output a single line containing YES if there exists an odd cycle in the remaining graph, or NO otherwise.

sample

3 3 2
1 2
2 3
3 1
2 2
4 5

NO
YES