[Solution] Qpwoeirut and Vertices Codeforces Solution

E. Qpwoeirut and Vertices

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a connected undirected graph with n$n$ vertices and m$m$ edges. Vertices of the graph are numbered by integers from 1$1$ to n$n$ and edges of the graph are numbered by integers from 1$1$ to m$m$.

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

• For all pairs of integers (a,b)$(a,b)$ such that l≤a≤b≤r$l\le a\le b\le r$, vertices a$a$ and b$b$ are reachable from one another using only the first k$k$ edges (that is, edges 1,2,…,k$1,2,\dots ,k$).

Input

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

The first line of each test case contains three integers n$n$, m$m$, and q$q$ (2≤n≤105$2\le n\le {10}^5$, 1≤m,q≤2⋅105$1\le m,q\le 2\cdot {10}^5$) — the

Solution Click Below:-  👉CLICK HERE

 number of vertices, edges, and queries respectively.

Each of the next m$m$ lines contains two integers ui$u_i$ and vi$v_i$ (1≤ui,vi≤n$1\le u_i,v_i\le n$) — ends of the i$i$-th edge.

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

Another String Minimization Problem Codeforces Solution

Making Towers Codeforces Solution

Qpwoeirut And The City Codeforces Solution

Chopping Carrots (Easy Version) Codeforces Solution

Chopping Carrots (Hard Version) Codeforces Solution

Each of the next q$q$ lines contains two integers l$l$ and r$r$ (1≤l≤r≤n$1\le l\le r\le n$) — descriptions of the queries.

It is guaranteed that that the sum of n$n$ over all test cases does not exceed 105${10}^5$, the sum of m$m$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$, and the sum of q$q$ over all test cases does not exceed 2⋅105$2\cdot {10}^5$.

Output

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