Codeforces Round 809 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

binary search

data structures

dfs and similar

divide and conquer

dsu

greedy

trees

*2300

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Qpwoeirut and Vertices

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputYou 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 $$$(a, b)$$$ 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, \ldots, 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.

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.

Example

Input

32 1 21 21 11 25 5 51 21 32 43 43 51 43 42 22 53 53 2 11 32 31 3

Output

0 1 3 3 0 5 5 2

Note

In the first test case, the graph contains $$$2$$$ vertices and a single edge connecting vertices $$$1$$$ and $$$2$$$.

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

In the second query, $$$l=1$$$ and $$$r=2$$$. Vertices $$$1$$$ and $$$2$$$ are reachable from one another using only the first edge, through the path $$$1 \longleftrightarrow 2$$$. It is impossible to reach vertex $$$2$$$ from vertex $$$1$$$ using only the first $$$0$$$ edges. So, the answer to this query is $$$1$$$.

In the second test case, the graph contains $$$5$$$ vertices and $$$5$$$ edges.

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

- Vertices $$$1$$$ and $$$2$$$ are reachable from one another through the path $$$1 \longleftrightarrow 2$$$ (edge $$$1$$$).
- Vertices $$$1$$$ and $$$3$$$ are reachable from one another through the path $$$1 \longleftrightarrow 3$$$ (edge $$$2$$$).
- Vertices $$$1$$$ and $$$4$$$ are reachable from one another through the path $$$1 \longleftrightarrow 2 \longleftrightarrow 4$$$ (edges $$$1$$$ and $$$3$$$).
- Vertices $$$2$$$ and $$$3$$$ are reachable from one another through the path $$$2 \longleftrightarrow 1 \longleftrightarrow 3$$$ (edges $$$1$$$ and $$$2$$$).
- Vertices $$$2$$$ and $$$4$$$ are reachable from one another through the path $$$2 \longleftrightarrow 4$$$ (edge $$$3$$$).
- Vertices $$$3$$$ and $$$4$$$ are reachable from one another through the path $$$3 \longleftrightarrow 1 \longleftrightarrow 2 \longleftrightarrow 4$$$ (edges $$$2$$$, $$$1$$$, and $$$3$$$).

If we use less than $$$3$$$ of the first edges, then the condition won't be satisfied. For example, it is impossible to reach vertex $$$4$$$ from vertex $$$1$$$ using only the first $$$2$$$ edges. So, the answer to this query is $$$3$$$.

In the second query, $$$l=3$$$ and $$$r=4$$$. Vertices $$$3$$$ and $$$4$$$ are reachable from one another through the path $$$3 \longleftrightarrow 1 \longleftrightarrow 2 \longleftrightarrow 4$$$ (edges $$$2$$$, $$$1$$$, and $$$3$$$). If we use any fewer of the first edges, nodes $$$3$$$ and $$$4$$$ will not be reachable from one another.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/23/2024 08:31:04 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|