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.
Table of Contents
[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).
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≤105, 1≤𝑚,𝑞≤2⋅1051≤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 2⋅1052⋅105, and the sum of 𝑞q over all test cases does not exceed 2⋅1052⋅105.
[Solution] Qpwoeirut and Vertices solution codeforces
For each test case, print 𝑞q integers — the answers to the queries.
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
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 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 1⟷21⟷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.[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 1⟷21⟷2 (edge 11).
- Vertices 11 and 33 are reachable from one another through the path 1⟷31⟷3 (edge 22).
- Vertices 11 and 44 are reachable from one another through the path 1⟷2⟷41⟷2⟷4 (edges 11 and 33).
- Vertices 22 and 33 are reachable from one another through the path 2⟷1⟷32⟷1⟷3 (edges 11 and 22).
- Vertices 22 and 44 are reachable from one another through the path 2⟷42⟷4 (edge 33).
- Vertices 33 and 44 are reachable from one another through the path 3⟷1⟷2⟷43⟷1⟷2⟷4 (edges 22, 11, 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 3⟷1⟷2⟷43⟷1⟷2⟷4 (edges 22, 11, and 33). If we use any fewer of the first edges, nodes 33 and 44 will not be reachable from one another.