ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

7580: Discovery of Cycles

内存限制：128 MB 时间限制：4 S
题面：传统 评测方式：文本比较 上传者：
提交：0 通过：0
提交提交记录统计Web Board

题目描述

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≤T≤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≤n,m,q≤3⋅105), 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 ui, vi (1≤ui,vi≤n, ui≠vi).

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


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

  • k1=(l′xorlastans)modm+1.

  • k2=(r′xorlastans)modm+1.

  • l=min(k1,k2).

  • r=max(k1,k2).



l and r means the edges in [l,r] will be chosen. That means, for this query, only edges (ul,vl),(ul+1,vl+1),…,(ur,vr) are visible.

It is guaranteed that ∑n,∑m≤1.5⋅106.

输出格式

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

分类标签