Discovery of Cycles

It is preferrable to read the pdf statment.

In response to the 8202 Olympics, Quber City, which was the host of the competition, is planning to build a magnificent stadium. The stadium is nowhere close to traditional stadiums that are typically embedded with a cyclic running trail. According to the plan, there are $n$ service spots in the stadium, and $m$ undirected running trails connecting them. Such adventurous design has brought worldwide attention to the stadium, but also comes with a huge cost.

Therefore the designers are working to simplify the design to cut down the cost. They discovered that the easiest way to do this is to sort the $m$ running trails in some particular order, and keep only some consecutive trails in the list. Since only part of the trails will be built, fund will be saved and everyone will be happy --- perhaps except those long-distance runners who needs a cyclic trail for the competition. A cyclic trail is a trail that starts at some service spot, passes through some distinct spots, before getting back to where it starts. All the running trails that have been used are required to be distinct. (This is by definition a simple cycle if you are familiar with terms in graph theory.)

Your task is to write a program that can quickly check, whether one can find at least one simple cycle, given that the stadium is built with some particular running trails selected consecutively from the trail list.

The first line of the input contains a single integer $T$ ($1\le T\le 10$), denoting the number of test cases.

For each of the next $T$ cases, the first line contains three space-separated integers $n$, $m$, $q$ ($1\le n,m,q \le 3\cdot 10^5$), denoting the number of service spots, number of running trails in the initial plan, and the number of queries.

In the next $m$ lines, the $i$-th line contains two space-separated integers $u_i$, $v_i$ ($1\le u_i,v_i\le n$, $u_i\ne v_i$).

Each of the next $q$ lines contains two space-separated integers $l'$, $r'$ ($1\le l'\le r'\le m$). $l$ and $r$ can be calculated via the following procedure.

• Let $\text{lastans}$ denote the answer to the last query (if the answer is ''Yes'', $\text{lastans} = 1$, otherwise $\text{lastans}=0$) and is initially zero.


• $k_1=(l'\; \text{xor}\; \text{lastans})\; \text{mod}\; m + 1$.


• $k_2=(r'\; \text{xor}\; \text{lastans})\; \text{mod}\; m + 1$.


• $l = \min(k_1, k_2)$.


• $r = \max(k_1, k_2)$.

$l$ and $r$ means the edges in $[l, r]$ will be chosen. That means, for this query, only edges $(u_l, v_l), (u_{l+1}, v_{l+1}), \ldots, (u_r, v_r)$ are visible.

It is guaranteed that $\sum n,\sum m \le 1.5\cdot 10^6$.

For every query, output ''Yes'' in one line if edges that are chosen forms at least one cyclic trail, otherwise output ''No'' in one line.

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

Yes
No
Yes

2020 Multi-University Training Contest 8