# [Solution] Qpwoeirut and Vertices solution codeforces

Qpwoeirut and Vertices solution codeforces – You are given a connected undirected graph with 𝑛n vertices and 𝑚m edges. Vertices of the graph are numbered by integers from 11 to 𝑛n and edges of the graph are numbered by integers from 11 to 𝑚m.

## [Solution] Qpwoeirut and Vertices solution codeforces

Your task is to answer 𝑞q queries, each consisting of two integers 𝑙l and 𝑟r. The answer to each query is the smallest non-negative integer 𝑘k such that the following condition holds:

• For all pairs of integers (𝑎,𝑏)(a,b) such that 𝑙𝑎𝑏𝑟l≤a≤b≤r, vertices 𝑎a and 𝑏b are reachable from one another using only the first 𝑘k edges (that is, edges 1,2,,𝑘1,2,…,k).
Input

The first line contains a single integer 𝑡t (1𝑡10001≤t≤1000) — the number of test cases.

The first line of each test case contains three integers 𝑛n𝑚m, and 𝑞q (2𝑛1052≤n≤1051𝑚,𝑞21051≤m,q≤2⋅105) — the number of vertices, edges, and queries respectively.

Each of the next 𝑚m lines contains two integers 𝑢𝑖ui and 𝑣𝑖vi (1𝑢𝑖,𝑣𝑖𝑛1≤ui,vi≤n) — ends of the 𝑖i-th edge.

It is guaranteed that the graph is connected and there are no multiple edges or self-loops.

Each of the next 𝑞q lines contains two integers 𝑙l and 𝑟r (1𝑙𝑟𝑛1≤l≤r≤n) — descriptions of the queries.

It is guaranteed that that the sum of 𝑛n over all test cases does not exceed 105105, the sum of 𝑚m over all test cases does not exceed 21052⋅105, and the sum of 𝑞q over all test cases does not exceed 21052⋅105.

## [Solution] Qpwoeirut and Vertices solution codeforces

For each test case, print 𝑞q integers — the answers to the queries.

Example
input

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

output

Copy
0 1
3 3 0 5 5
2


## [Solution] Qpwoeirut and Vertices solution codeforces Graph from the first test case. The integer near the edge is its number.
In the first test case, the graph contains 22 vertices and a single edge connecting vertices 11 and 22.

In the first query, 𝑙=1l=1 and 𝑟=1r=1. It is possible to reach any vertex from itself, so the answer to this query is 00.

In the second query, 𝑙=1l=1 and 𝑟=2r=2. Vertices 11 and 22 are reachable from one another using only the first edge, through the path 121⟷2. It is impossible to reach vertex 22 from vertex 11 using only the first 00 edges. So, the answer to this query is 11. Graph from the second test case. The integer near the edge is its number.
In the second test case, the graph contains 55 vertices and 55 edges.

## [Solution] Qpwoeirut and Vertices solution codeforces

In the first query, 𝑙=1l=1 and 𝑟=4r=4. It is enough to use the first 33 edges to satisfy the condition from the statement:

• Vertices 11 and 22 are reachable from one another through the path 121⟷2 (edge 11).
• Vertices 11 and 33 are reachable from one another through the path 131⟷3 (edge 22).
• Vertices 11 and 44 are reachable from one another through the path 1241⟷2⟷4 (edges 11 and 33).
• Vertices 22 and 33 are reachable from one another through the path 2132⟷1⟷3 (edges 11 and 22).
• Vertices 22 and 44 are reachable from one another through the path 242⟷4 (edge 33).
• Vertices 33 and 44 are reachable from one another through the path 31243⟷1⟷2⟷4 (edges 2211, and 33).

If we use less than 33 of the first edges, then the condition won’t be satisfied. For example, it is impossible to reach vertex 44 from vertex 11 using only the first 22 edges. So, the answer to this query is 33.

In the second query, 𝑙=3l=3 and 𝑟=4r=4. Vertices 33 and 44 are reachable from one another through the path 31243⟷1⟷2⟷4 (edges 2211, and 33). If we use any fewer of the first edges, nodes 33 and 44 will not be reachable from one another.