## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

# [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$ vertices and $m$ edges. Vertices of the graph are numbered by integers from $1$ to $n$ and edges of the graph are numbered by integers from $1$ to $m$.

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 $\left(a,b\right)$ such that $l\le a\le b\le r$, vertices $a$ and $b$ are reachable from one another using only the first $k$ edges (that is, edges $1,2,\dots ,k$).
Input

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

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

number of vertices, edges, and queries respectively.

Each of the next $m$ lines contains two integers ${u}_{i}$ and ${v}_{i}$ ($1\le {u}_{i},{v}_{i}\le n$) — ends of the $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$ lines contains two integers $l$ and $r$ ($1\le l\le r\le n$) — descriptions of the queries.

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

Output

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