Qpwoeirut and Vertices (Codeforces 1706E)
Tags: Greedy, divide and conquer

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 $$$(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.

Note:   Graph from the first test case. The integer near the edge is its number. 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$$$.  Graph from the second test case. The integer near the edge is its number. 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.

Sample Inputs:
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

Sample Outputs:
0 1 
3 3 0 5 5 
2

Solution (Python):
class UnionFind:

    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, a):
        acopy = a
        while a != self.parent[a]:
            a = self.parent[a]
        while acopy != a:
            (self.parent[acopy], acopy) = (a, self.parent[acopy])
        return a

    def union(self, a, b):
        self.parent[self.find(b)] = self.find(a)

class RMQMAX:

    def __init__(self, arr):
        self.arr = arr
        MAXN = len(arr)
        self.log2 = [0] * (MAXN + 1)
        i = 0
        while 2 ** i < MAXN + 1:
            self.log2[2 ** i] = i
            i += 1
        for i in range(1, MAXN + 1):
            if self.log2[i] == 0:
                self.log2[i] = self.log2[i - 1]
        K = self.log2[MAXN] + 1
        self.lookup = [0] * ((K + 1) * MAXN)
        self.M = K + 1
        self.buildSparseTable()

    def buildSparseTable(self):
        n = len(self.arr)
        for i in range(0, n):
            self.lookup[i * self.M] = self.arr[i]
        j = 1
        while 1 << j <= n:
            i = 0
            while i + (1 << j) - 1 < n:
                self.lookup[i * self.M + j] = max(self.lookup[i * self.M + j - 1], self.lookup[(i + (1 << j - 1)) * self.M + j - 1])
                i += 1
            j += 1

    def query(self, L, R):
        j = self.log2[R - L + 1]
        return max(self.lookup[L * self.M + j], self.lookup[(R - (1 << j) + 1) * self.M + j])

def main():
    t = int(input())
    allans = []
    for _ in range(t):
        (n, m, q) = readIntArr()
        min_time = [-1] * (n - 1)
        uf = UnionFind(n)
        groups = [set([i]) for i in range(n)]
        for j in range(m):
            (u, v) = readIntArr()
            u -= 1
            v -= 1
            if len(groups[uf.find(u)]) > len(groups[uf.find(v)]):
                (u, v) = (v, u)
            (paru, parv) = (uf.find(u), uf.find(v))
            if paru == parv:
                continue
            uf.parent[paru] = parv
            while groups[paru]:
                z = groups[paru].pop()
                groups[parv].add(z)
                if z - 1 in groups[parv] and min_time[z - 1] == -1:
                    min_time[z - 1] = j + 1
                if z + 1 in groups[parv] and min_time[z] == -1:
                    min_time[z] = j + 1
        rmq = RMQMAX(min_time)
        ans = [-1] * q
        for i in range(q):
            (l, r) = readIntArr()
            l -= 1
            r -= 1
            if l == r:
                ans[i] = 0
            else:
                ans[i] = rmq.query(l, r - 1)
        allans.append(ans)
    multiLineArrayOfArraysPrint(allans)
    return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
    print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
    print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
    print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
    return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
    dv = defaultValFactory
    da = dimensionArr
    if len(da) == 1:
        return [dv() for _ in range(da[0])]
    else:
        return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(a, b, c):
    print('? {} {} {}'.format(a, b, c))
    sys.stdout.flush()
    return int(input())

def answerInteractive(x1, x2):
    print('! {} {}'.format(x1, x2))
    sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
import math
for _abc in range(1):
    main()

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def get_root(s):
    v = []
    while not s == root[s]:
        v.append(s)
        s = root[s]
    for i in v:
        root[i] = s
    return s

def unite(s, t):
    (rs, rt) = (get_root(s), get_root(t))
    if not rs ^ rt:
        return 0
    if get_size(rs) >= get_size(rt):
        root[rt] = rs
        size[rs] += size[rt]
        return rs
    else:
        root[rs] = rt
        size[rt] += size[rs]
        return rt

def same(s, t):
    return True if get_root(s) == get_root(t) else False

def get_size(s):
    return size[get_root(s)]

def sparse_table(a):
    table = []
    (s0, l) = (a, 1)
    table.append(s0)
    while 2 * l <= len(a):
        s = [max(s0[i], s0[i + l]) for i in range(len(s0) - l)]
        table.append(list(s))
        s0 = s
        l *= 2
    return table

def get_max(l, r, table):
    d = len(bin(r - l + 1)) - 3
    ans = max(table[d][l], table[d][r - pow2[d] + 1])
    return ans
t = int(input())
ans = []
pow2 = [1]
for _ in range(20):
    pow2.append(2 * pow2[-1])
inf = pow(10, 9) + 1
for _ in range(t):
    (n, m, q) = map(int, input().split())
    root = [i for i in range(n + 1)]
    rank = [1 for _ in range(n + 1)]
    size = [1 for _ in range(n + 1)]
    x = [inf] * (n + 1)
    s = [set() for _ in range(n + 1)]
    for i in range(1, n + 1):
        s[i].add(i)
    for i in range(m):
        (u, v) = map(int, input().split())
        if same(u, v):
            continue
        (ru, rv) = (get_root(u), get_root(v))
        if get_size(ru) < get_size(rv):
            (u, v) = (v, u)
            (ru, rv) = (rv, ru)
        while s[rv]:
            k = s[rv].pop()
            if k - 1 in s[ru]:
                x[k - 1] = min(x[k - 1], i + 1)
            if k + 1 in s[ru]:
                x[k] = min(x[k], i + 1)
            s[ru].add(k)
        unite(u, v)
    table = sparse_table(x)
    ans1 = []
    for _ in range(q):
        (l, r) = map(int, input().split())
        ans0 = 0 if l == r else get_max(l, r - 1, table)
        ans1.append(ans0)
    ans.append(' '.join(map(str, ans1)))
sys.stdout.write('\n'.join(ans))

Solution (Python):
from collections import deque

class DisjointSetUnion:

    def __init__(self, n):
        self.root = [-1] * n

    def find(self, x):
        y = x
        while self.root[x] >= 0:
            x = self.root[x]
        while y != x:
            (self.root[y], y) = (x, self.root[y])
        return x

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return 0
        if self.root[x] > self.root[y]:
            self.root[y] += self.root[x]
            self.root[x] = y
        else:
            self.root[x] += self.root[y]
            self.root[y] = x
        return 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

class RangeQuery:

    def __init__(self, data, func=min):
        self.func = func
        self._data = _data = [list(data)]
        (i, n) = (1, len(_data[0]))
        while 2 * i <= n:
            prev = _data[-1]
            _data.append([func(prev[j], prev[j + i]) for j in range(n - 2 * i + 1)])
            i <<= 1

    def query(self, start, stop):
        """"""
        depth = (stop - start).bit_length() - 1
        return self.func(self._data[depth][start], self._data[depth][stop - (1 << depth)])

    def __getitem__(self, idx):
        return self._data[0][idx]

def solve():
    (n, m, q) = map(int, input().split())
    g = [[] for i in range(n)]
    dsu = DisjointSetUnion(n)
    for i in range(1, m + 1):
        (x, y) = map(int, input().split())
        x -= 1
        y -= 1
        if dsu.union(x, y):
            g[x].append((y, i))
            g[y].append((x, i))
    prev = [0] * n
    depth = [-1] * n
    depth[0] = 0
    val = [0] * n
    queue = deque()
    queue.append(0)
    while queue:
        x = queue.popleft()
        d = depth[x] + 1
        for (y, m) in g[x]:
            if depth[y] == -1:
                depth[y] = d
                prev[y] = x
                val[y] = m
                queue.append(y)
    up = [prev]
    mup = [val]
    for i in range(17):
        up.append([prev[prev[j]] for j in range(n)])
        mup.append([max(val[j], val[prev[j]]) for j in range(n)])
        prev = up[-1]
        val = mup[-1]

    def lca(x, y):
        if depth[x] > depth[y]:
            (x, y) = (y, x)
        d = depth[y] - depth[x]
        for i in range(17):
            if d >> i & 1:
                y = up[i][y]
        if x == y:
            return x
        for i in range(16, -1, -1):
            (a, b) = (up[i][x], up[i][y])
            if a != b:
                (x, y) = (a, b)
        return up[0][x]

    def ma(x, y):
        a = lca(x, y)
        d = depth[x] - depth[a]
        ans = 0
        for i in range(17):
            if d >> i & 1:
                ans = max(ans, mup[i][x])
                x = up[i][x]
        d = depth[y] - depth[a]
        for i in range(17):
            if d >> i & 1:
                ans = max(ans, mup[i][y])
                y = up[i][y]
        return ans
    rmq = RangeQuery([ma(i, i + 1) for i in range(n - 1)], max)
    ans = []
    for ii in range(q):
        (x, y) = map(int, input().split())
        if x == y:
            ans.append(0)
            continue
        if x > y:
            (x, y) = (y, x)
        ans.append(rmq.query(x - 1, y - 1))
    print(*ans)
import sys
input = lambda : sys.stdin.readline().rstrip()
t = int(input())
for i in range(t):
    solve()