Company (Codeforces 1062E)
Tags: Greedy, trees

The company $$$X$$$ has $$$n$$$ employees numbered from $$$1$$$ through $$$n$$$. Each employee $$$u$$$ has a direct boss $$$p_u$$$ ($$$1 \le p_u \le n$$$), except for the employee $$$1$$$ who has no boss. It is guaranteed, that values $$$p_i$$$ form a tree. Employee $$$u$$$ is said to be in charge of employee $$$v$$$ if $$$u$$$ is the direct boss of $$$v$$$ or there is an employee $$$w$$$ such that $$$w$$$ is in charge of $$$v$$$ and $$$u$$$ is the direct boss of $$$w$$$. Also, any employee is considered to be in charge of himself.In addition, for each employee $$$u$$$ we define it's level $$$lv(u)$$$ as follow:   $$$lv(1)=0$$$  $$$lv(u)=lv(p_u)+1$$$ for $$$u \neq 1$$$ In the near future, there are $$$q$$$ possible plans for the company to operate. The $$$i$$$-th plan consists of two integers $$$l_i$$$ and $$$r_i$$$, meaning that all the employees in the range $$$[l_i, r_i]$$$, and only they, are involved in this plan. To operate the plan smoothly, there must be a project manager who is an employee in charge of all the involved employees. To be precise, if an employee $$$u$$$ is chosen as the project manager for the $$$i$$$-th plan then for every employee $$$v \in [l_i, r_i]$$$, $$$u$$$ must be in charge of $$$v$$$. Note, that $$$u$$$ is not necessary in the range $$$[l_i, r_i]$$$. Also, $$$u$$$ is always chosen in such a way that $$$lv(u)$$$ is as large as possible (the higher the level is, the lower the salary that the company has to pay the employee).Before any plan is operated, the company has JATC take a look at their plans. After a glance, he tells the company that for every plan, it's possible to reduce the number of the involved employees exactly by one without affecting the plan. Being greedy, the company asks JATC which employee they should kick out of the plan so that the level of the project manager required is as large as possible. JATC has already figured out the answer and challenges you to do the same.

Input: The first line contains two integers $$$n$$$ and $$$q$$$ ($$$2 \le n \le 100\,000$$$, $$$1 \le q \le 100\,000$$$) — the number of employees and the number of plans, respectively.The second line contains $$$n-1$$$ integers $$$p_2, p_3, \dots, p_n$$$ ($$$1 \le p_i \le n$$$) meaning $$$p_i$$$ is the direct boss of employee $$$i$$$.It is guaranteed, that values $$$p_i$$$ form a directed tree with the root of $$$1$$$.Each of the following $$$q$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i<r_i \le n$$$) — the range of the employees, involved in the corresponding plan.

Output: Print $$$q$$$ lines, each containing two integers — the number of the employee which should be kicked from the corresponding plan and the maximum possible level of the project manager in that case.If there are more than one way to choose that employee, print any of them.

Note: In the example:    In the first query, we can choose whether $$$4$$$ or $$$5$$$ or $$$6$$$ and the project manager will be $$$3$$$.In the second query, if we choose any employee other than the employee $$$8$$$, the project manager will be $$$1$$$. If we choose $$$8$$$, the project manager will be $$$3$$$. Since $$$lv(3)=1 > lv(1)=0$$$, choosing $$$8$$$ is the best strategy.In the third query, no matter how we choose the employee, the project manager will always be $$$1$$$.In the fourth query, if we choose $$$9$$$ or $$$10$$$ then the project manager will be $$$3$$$. If we choose $$$11$$$ then the project manager will be $$$7$$$. Since $$$lv(7)=3>lv(3)=1$$$, we choose $$$11$$$ as the answer.

Sample Inputs:
11 5
1 1 3 3 3 4 2 7 7 6
4 6
4 8
1 11
9 11
8 11

Sample Outputs:
4 1
8 1
1 0
11 3
8 1

Solution (Python):
import sys
input = sys.stdin.buffer.readline

class RangeQuery:

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

    def query(self, begin, end):
        depth = (end - begin).bit_length() - 1
        return min(self._data[depth][begin], self._data[depth][end - (1 << depth)])

def lca(depths, time, path, rmq, x, y):
    t1 = time[x]
    t2 = time[y]
    (t1, t2) = (min(t1, t2), max(t1, t2))
    return depths[path[rmq.query(t1, t2)]]

def process(n, G, Q):
    depths = [-1 for i in range(n + 1)]
    time = [-1 for i in range(n + 1)]
    path = [-1 for i in range(n + 1)]
    P = [-1 for i in range(n + 1)]
    g = [[] for i in range(n + 1)]
    for i in range(2, n + 1):
        pi = G[i - 2]
        g[pi].append(i)
        g[i].append(pi)
    dfs = [1]
    depths[1] = 0
    t = -1
    while dfs:
        node = dfs.pop()
        path[t] = P[node]
        time[node] = t = t + 1
        for nei in g[node]:
            if time[nei] == -1:
                depths[nei] = depths[node] + 1
                P[nei] = node
                dfs.append(nei)
    rmq = RangeQuery((time[node] for node in path))
    consec = [[-1, 0]]
    for i in range(1, n):
        d = lca(depths, time, path, rmq, i, i + 1)
        consec.append([d, i])
    rmq2 = RangeQuery(consec)
    for (l, r) in Q:
        answer = [-1, None]
        if l + 1 == r:
            answer = max(answer, [depths[r], l], [depths[l], r])
        else:
            (d1, i1) = rmq2.query(l, r)
            answer = max(answer, [d1, l])
            d2 = lca(depths, time, path, rmq, l, r)
            for to_remove in [i1, i1 + 1]:
                x = float('inf')
                if to_remove - 1 >= l and to_remove + 1 <= r:
                    x = min(x, lca(depths, time, path, rmq, to_remove - 1, to_remove + 1))
                if to_remove - 1 > l:
                    x = min(x, rmq2.query(l, to_remove - 1)[0])
                if to_remove + 1 < r:
                    x = min(x, rmq2.query(to_remove + 1, r)[0])
                if to_remove != l and to_remove != r:
                    x = min(x, d2)
                answer = max(answer, [x, to_remove])
        sys.stdout.write(f'{answer[1]} {answer[0]}\n')
    return
(n, q) = [int(x) for x in input().split()]
G = [int(x) for x in input().split()]
Q = []
for i in range(q):
    (l, r) = [int(x) for x in input().split()]
    Q.append([l, r])
process(n, G, Q)

Solution (Python):
import sys
readline = sys.stdin.readline

class Graph:

    def __init__(self, V, edges=False, graph=False, directed=False, weighted=False, inf=float('inf')):
        self.V = V
        self.directed = directed
        self.weighted = weighted
        self.inf = inf
        if graph:
            self.graph = graph
            self.edges = []
            for i in range(self.V):
                if self.weighted:
                    for (j, d) in self.graph[i]:
                        if self.directed or (not self.directed and i <= j):
                            self.edges.append((i, j, d))
                else:
                    for j in self.graph[i]:
                        if self.directed or (not self.directed and i <= j):
                            self.edges.append((i, j))
        else:
            self.edges = edges
            self.graph = [[] for i in range(self.V)]
            if weighted:
                for (i, j, d) in self.edges:
                    self.graph[i].append((j, d))
                    if not self.directed:
                        self.graph[j].append((i, d))
            else:
                for (i, j) in self.edges:
                    self.graph[i].append(j)
                    if not self.directed:
                        self.graph[j].append(i)

    def SIV_BFS(self, s, bfs_tour=False, bipartite_graph=False, linked_components=False, parents=False, unweighted_dist=False, weighted_dist=False):
        seen = [False] * self.V
        seen[s] = True
        if bfs_tour:
            bt = [s]
        if linked_components:
            lc = [s]
        if parents:
            ps = [None] * self.V
        if unweighted_dist or bipartite_graph:
            uwd = [self.inf] * self.V
            uwd[s] = 0
        if weighted_dist:
            wd = [self.inf] * self.V
            wd[s] = 0
        queue = deque([s])
        while queue:
            x = queue.popleft()
            for y in self.graph[x]:
                if self.weighted:
                    (y, d) = y
                if not seen[y]:
                    seen[y] = True
                    queue.append(y)
                    if bfs_tour:
                        bt.append(y)
                    if linked_components:
                        lc.append(y)
                    if parents:
                        ps[y] = x
                    if unweighted_dist or bipartite_graph:
                        uwd[y] = uwd[x] + 1
                    if weighted_dist:
                        wd[y] = wd[x] + d
        if bipartite_graph:
            bg = [[], []]
            for tpl in self.edges:
                (i, j) = tpl[:2] if self.weighted else tpl
                if uwd[i] == self.inf or uwd[j] == self.inf:
                    continue
                if not uwd[i] % 2 ^ uwd[j] % 2:
                    bg = False
                    break
            else:
                for x in range(self.V):
                    if uwd[x] == self.inf:
                        continue
                    bg[uwd[x] % 2].append(x)
        retu = ()
        if bfs_tour:
            retu += (bt,)
        if bipartite_graph:
            retu += (bg,)
        if linked_components:
            retu += (lc,)
        if parents:
            retu += (ps,)
        if unweighted_dist:
            retu += (uwd,)
        if weighted_dist:
            retu += (wd,)
        if len(retu) == 1:
            retu = retu[0]
        return retu

    def MIV_BFS(self, initial_vertices=None, bipartite_graph=False, linked_components=False, parents=False, unweighted_dist=False, weighted_dist=False):
        if initial_vertices == None:
            initial_vertices = [i for i in range(self.V)]
        seen = [False] * self.V
        if bipartite_graph:
            bg = [None] * self.V
            cnt = -1
        if linked_components:
            lc = []
        if parents:
            ps = [None] * self.V
        if unweighted_dist:
            uwd = [self.inf] * self.V
        if weighted_dist:
            wd = [self.inf] * self.V
        for s in initial_vertices:
            if seen[s]:
                continue
            seen[s] = True
            if bipartite_graph:
                cnt += 1
                bg[s] = (cnt, 0)
            if linked_components:
                lc.append([s])
            if unweighted_dist:
                uwd[s] = 0
            if weighted_dist:
                wd[s] = 0
            queue = deque([s])
            while queue:
                x = queue.popleft()
                for y in self.graph[x]:
                    if self.weighted:
                        (y, d) = y
                    if not seen[y]:
                        seen[y] = True
                        queue.append(y)
                        if bipartite_graph:
                            bg[y] = (cnt, bg[x][1] ^ 1)
                        if linked_components:
                            lc[-1].append(y)
                        if parents:
                            ps[y] = x
                        if unweighted_dist:
                            uwd[y] = uwd[x] + 1
                        if weighted_dist:
                            wd[y] = wd[x] + d
        if bipartite_graph:
            bg_ = bg
            bg = [[[], []] for i in range(cnt + 1)]
            for tpl in self.edges:
                (i, j) = tpl[:2] if self.weighted else tpl
                if not bg_[i][1] ^ bg_[j][1]:
                    bg[bg_[i][0]] = False
            for x in range(self.V):
                if bg[bg_[x][0]]:
                    bg[bg_[x][0]][bg_[x][1]].append(x)
        retu = ()
        if bipartite_graph:
            retu += (bg,)
        if linked_components:
            retu += (lc,)
        if parents:
            retu = (ps,)
        if unweighted_dist:
            retu += (uwd,)
        if weighted_dist:
            retu += (wd,)
        if len(retu) == 1:
            retu = retu[0]
        return retu

    def SIV_DFS(self, s, bipartite_graph=False, cycle_detection=False, directed_acyclic=False, euler_tour=False, linked_components=False, lowlink=False, parents=False, postorder=False, preorder=False, subtree_size=False, topological_sort=False, unweighted_dist=False, weighted_dist=False):
        seen = [False] * self.V
        finished = [False] * self.V
        if directed_acyclic or cycle_detection or topological_sort:
            dag = True
        if euler_tour:
            et = []
        if linked_components:
            lc = []
        if lowlink:
            order = [None] * self.V
            ll = [None] * self.V
            idx = 0
        if parents or cycle_detection or lowlink or subtree_size:
            ps = [None] * self.V
        if postorder or topological_sort:
            post = []
        if preorder:
            pre = []
        if subtree_size:
            ss = [1] * self.V
        if unweighted_dist or bipartite_graph:
            uwd = [self.inf] * self.V
            uwd[s] = 0
        if weighted_dist:
            wd = [self.inf] * self.V
            wd[s] = 0
        stack = [(s, 0)] if self.weighted else [s]
        while stack:
            if self.weighted:
                (x, d) = stack.pop()
            else:
                x = stack.pop()
            if not seen[x]:
                seen[x] = True
                stack.append((x, d) if self.weighted else x)
                if euler_tour:
                    et.append(x)
                if linked_components:
                    lc.append(x)
                if lowlink:
                    order[x] = idx
                    ll[x] = idx
                    idx += 1
                if preorder:
                    pre.append(x)
                for y in self.graph[x]:
                    if self.weighted:
                        (y, d) = y
                    if not seen[y]:
                        stack.append((y, d) if self.weighted else y)
                        if parents or cycle_detection or lowlink or subtree_size:
                            ps[y] = x
                        if unweighted_dist or bipartite_graph:
                            uwd[y] = uwd[x] + 1
                        if weighted_dist:
                            wd[y] = wd[x] + d
                    elif not finished[y]:
                        if (directed_acyclic or cycle_detection or topological_sort) and dag:
                            dag = False
                            if cycle_detection:
                                cd = (y, x)
            elif not finished[x]:
                finished[x] = True
                if euler_tour:
                    et.append(~x)
                if lowlink:
                    bl = True
                    for y in self.graph[x]:
                        if self.weighted:
                            (y, d) = y
                        if ps[x] == y and bl:
                            bl = False
                            continue
                        ll[x] = min(ll[x], order[y])
                    if x != s:
                        ll[ps[x]] = min(ll[ps[x]], ll[x])
                if postorder or topological_sort:
                    post.append(x)
                if subtree_size:
                    for y in self.graph[x]:
                        if self.weighted:
                            (y, d) = y
                        if y == ps[x]:
                            continue
                        ss[x] += ss[y]
        if bipartite_graph:
            bg = [[], []]
            for tpl in self.edges:
                (x, y) = tpl[:2] if self.weighted else tpl
                if uwd[x] == self.inf or uwd[y] == self.inf:
                    continue
                if not uwd[x] % 2 ^ uwd[y] % 2:
                    bg = False
                    break
            else:
                for x in range(self.V):
                    if uwd[x] == self.inf:
                        continue
                    bg[uwd[x] % 2].append(x)
        retu = ()
        if bipartite_graph:
            retu += (bg,)
        if cycle_detection:
            if dag:
                cd = []
            else:
                (y, x) = cd
                cd = self.Route_Restoration(y, x, ps)
            retu += (cd,)
        if directed_acyclic:
            retu += (dag,)
        if euler_tour:
            retu += (et,)
        if linked_components:
            retu += (lc,)
        if lowlink:
            retu = (ll,)
        if parents:
            retu += (ps,)
        if postorder:
            retu += (post,)
        if preorder:
            retu += (pre,)
        if subtree_size:
            retu += (ss,)
        if topological_sort:
            if dag:
                tp_sort = post[::-1]
            else:
                tp_sort = []
            retu += (tp_sort,)
        if unweighted_dist:
            retu += (uwd,)
        if weighted_dist:
            retu += (wd,)
        if len(retu) == 1:
            retu = retu[0]
        return retu

    def MIV_DFS(self, initial_vertices=None, bipartite_graph=False, cycle_detection=False, directed_acyclic=False, euler_tour=False, linked_components=False, lowlink=False, parents=False, postorder=False, preorder=False, subtree_size=False, topological_sort=False, unweighted_dist=False, weighted_dist=False):
        if initial_vertices == None:
            initial_vertices = [s for s in range(self.V)]
        seen = [False] * self.V
        finished = [False] * self.V
        if bipartite_graph:
            bg = [None] * self.V
            cnt = -1
        if directed_acyclic or cycle_detection or topological_sort:
            dag = True
        if euler_tour:
            et = []
        if linked_components:
            lc = []
        if lowlink:
            order = [None] * self.V
            ll = [None] * self.V
            idx = 0
        if parents or cycle_detection or lowlink or subtree_size:
            ps = [None] * self.V
        if postorder or topological_sort:
            post = []
        if preorder:
            pre = []
        if subtree_size:
            ss = [1] * self.V
        if unweighted_dist:
            uwd = [self.inf] * self.V
        if weighted_dist:
            wd = [self.inf] * self.V
        for s in initial_vertices:
            if seen[s]:
                continue
            if bipartite_graph:
                cnt += 1
                bg[s] = (cnt, 0)
            if linked_components:
                lc.append([])
            if unweighted_dist:
                uwd[s] = 0
            if weighted_dist:
                wd[s] = 0
            stack = [(s, 0)] if self.weighted else [s]
            while stack:
                if self.weighted:
                    (x, d) = stack.pop()
                else:
                    x = stack.pop()
                if not seen[x]:
                    seen[x] = True
                    stack.append((x, d) if self.weighted else x)
                    if euler_tour:
                        et.append(x)
                    if linked_components:
                        lc[-1].append(x)
                    if lowlink:
                        order[x] = idx
                        ll[x] = idx
                        idx += 1
                    if preorder:
                        pre.append(x)
                    for y in self.graph[x]:
                        if self.weighted:
                            (y, d) = y
                        if not seen[y]:
                            stack.append((y, d) if self.weighted else y)
                            if bipartite_graph:
                                bg[y] = (cnt, bg[x][1] ^ 1)
                            if parents or cycle_detection or lowlink or subtree_size:
                                ps[y] = x
                            if unweighted_dist or bipartite_graph:
                                uwd[y] = uwd[x] + 1
                            if weighted_dist:
                                wd[y] = wd[x] + d
                        elif not finished[y]:
                            if directed_acyclic and dag:
                                dag = False
                                if cycle_detection:
                                    cd = (y, x)
                elif not finished[x]:
                    finished[x] = True
                    if euler_tour:
                        et.append(~x)
                    if lowlink:
                        bl = True
                        for y in self.graph[x]:
                            if self.weighted:
                                (y, d) = y
                            if ps[x] == y and bl:
                                bl = False
                                continue
                            ll[x] = min(ll[x], order[y])
                        if x != s:
                            ll[ps[x]] = min(ll[ps[x]], ll[x])
                    if postorder or topological_sort:
                        post.append(x)
                    if subtree_size:
                        for y in self.graph[x]:
                            if self.weighted:
                                (y, d) = y
                            if y == ps[x]:
                                continue
                            ss[x] += ss[y]
        if bipartite_graph:
            bg_ = bg
            bg = [[[], []] for i in range(cnt + 1)]
            for tpl in self.edges:
                (i, j) = tpl[:2] if self.weighted else tpl
                if not bg_[i][1] ^ bg_[j][1]:
                    bg[bg_[i][0]] = False
            for x in range(self.V):
                if bg[bg_[x][0]]:
                    bg[bg_[x][0]][bg_[x][1]].append(x)
        retu = ()
        if bipartite_graph:
            retu += (bg,)
        if cycle_detection:
            if dag:
                cd = []
            else:
                (y, x) = cd
                cd = self.Route_Restoration(y, x, ps)
            retu += (cd,)
        if directed_acyclic:
            retu += (dag,)
        if euler_tour:
            retu += (et,)
        if linked_components:
            retu += (lc,)
        if lowlink:
            retu = (ll,)
        if parents:
            retu += (ps,)
        if postorder:
            retu += (post,)
        if preorder:
            retu += (pre,)
        if subtree_size:
            retu += (ss,)
        if topological_sort:
            if dag:
                tp_sort = post[::-1]
            else:
                tp_sort = []
            retu += (tp_sort,)
        if unweighted_dist:
            retu += (uwd,)
        if weighted_dist:
            retu += (wd,)
        if len(retu) == 1:
            retu = retu[0]
        return retu

    def Tree_Diameter(self, weighted=False):

        def Farthest_Point(u):
            dist = self.SIV_BFS(u, weighted_dist=True) if weighted else self.SIV_BFS(u, unweighted_dist=True)
            fp = 0
            for i in range(self.V):
                if dist[fp] < dist[i]:
                    fp = i
            return (fp, dist[fp])
        (u, d) = Farthest_Point(0)
        (v, d) = Farthest_Point(u)
        return (u, v, d)

    def SCC(self):
        reverse_graph = [[] for i in range(self.V)]
        for tpl in self.edges:
            (u, v) = tpl[:2] if self.weighted else tpl
            reverse_graph[v].append(u)
        postorder = self.MIV_DFS(postorder=True)
        scc_points = []
        seen = [False] * self.V
        for s in postorder[::-1]:
            if seen[s]:
                continue
            queue = deque([s])
            seen[s] = True
            lst = []
            while queue:
                x = queue.popleft()
                lst.append(x)
                for y in reverse_graph[x]:
                    if not seen[y]:
                        seen[y] = True
                        queue.append(y)
            scc_points.append(lst)
        l = len(scc_points)
        idx = [None] * self.V
        for i in range(l):
            for x in scc_points[i]:
                idx[x] = i
        scc_edges = set()
        for tpl in self.edges:
            (u, v) = tpl[:2] if self.weighted else tpl
            if idx[u] != idx[v]:
                scc_edges.add((idx[u], idx[v]))
        scc_edges = list(scc_edges)
        return (scc_points, scc_edges)

    def Build_LCA(self, s):
        (self.lca_euler_tour, self.lca_parents, depth) = self.SIV_DFS(s, euler_tour=True, parents=True, unweighted_dist=True)
        self.lca_dfs_in_index = [None] * self.V
        self.lca_dfs_out_index = [None] * self.V
        for (i, x) in enumerate(self.lca_euler_tour):
            if x >= 0:
                self.lca_dfs_in_index[x] = i
            else:
                self.lca_dfs_out_index[~x] = i
        self.ST = Segment_Tree(2 * self.V, lambda x, y: min(x, y), self.V)
        lst = [None] * (2 * self.V)
        for i in range(2 * self.V - 1):
            if self.lca_euler_tour[i] >= 0:
                lst[i] = depth[self.lca_euler_tour[i]]
            else:
                lst[i] = depth[self.lca_parents[~self.lca_euler_tour[i]]]
        lst[2 * self.V - 1] = -1
        self.ST.Build(lst)

    def LCA(self, a, b):
        m = min(self.lca_dfs_in_index[a], self.lca_dfs_in_index[b])
        M = max(self.lca_dfs_in_index[a], self.lca_dfs_in_index[b])
        x = self.lca_euler_tour[self.ST.Fold_Index(m, M + 1)]
        if x >= 0:
            return x
        else:
            return self.lca_parents[~x]

    def Build_HLD(self, s):
        (self.hld_parents, size, self.hld_depth) = self.SIV_DFS(s, parents=True, subtree_size=True, unweighted_dist=True)
        stack = [s]
        self.hld_tour = []
        self.hld_path_parents = [None] * self.V
        self.hld_path_parents[s] = s
        while stack:
            x = stack.pop()
            self.hld_tour.append(x)
            max_size = 0
            max_size_y = None
            for y in self.graph[x]:
                if self.weighted:
                    (y, d) = y
                if y == self.hld_parents[x]:
                    continue
                if max_size < size[y]:
                    max_size = size[y]
                    max_size_y = y
            for y in self.graph[x]:
                if self.weighted:
                    (y, d) = y
                if y == self.hld_parents[x]:
                    continue
                if y != max_size_y:
                    stack.append(y)
                    self.hld_path_parents[y] = y
            if max_size_y != None:
                stack.append(max_size_y)
                self.hld_path_parents[max_size_y] = self.hld_path_parents[x]
        self.hld_tour_idx = [None] * self.V
        for i in range(self.V):
            self.hld_tour_idx[self.hld_tour[i]] = i

    def HLD(self, a, b, edge=False):
        (L, R) = ([], [])
        while self.hld_path_parents[a] != self.hld_path_parents[b]:
            if self.hld_depth[self.hld_path_parents[a]] < self.hld_depth[self.hld_path_parents[b]]:
                R.append((self.hld_tour_idx[self.hld_path_parents[b]], self.hld_tour_idx[b] + 1))
                b = self.hld_parents[self.hld_path_parents[b]]
            else:
                L.append((self.hld_tour_idx[a] + 1, self.hld_tour_idx[self.hld_path_parents[a]]))
                a = self.hld_parents[self.hld_path_parents[a]]
        if edge:
            if self.hld_depth[a] != self.hld_depth[b]:
                retu = L + [(self.hld_tour_idx[a] + 1, self.hld_tour_idx[b] + 1)] + R[::-1]
            else:
                retu = L + R[::-1]
        elif self.hld_depth[a] < self.hld_depth[b]:
            retu = L + [(self.hld_tour_idx[a], self.hld_tour_idx[b] + 1)] + R[::-1]
        else:
            retu = L + [(self.hld_tour_idx[a] + 1, self.hld_tour_idx[b])] + R[::-1]
        return retu

    def Build_Hash(self, s, random_number=False, mod=(1 << 61) - 1, rerooting=False):
        self.bottom_hash = [None] * self.V
        if random_number:
            self.hash_random_number = random_number
        else:
            self.hash_random_number = [random.randint(1, 10 ** 10) for i in range(self.V)]
        self.hash_mod = mod
        (parents, postorder, preorder) = self.SIV_DFS(s, parents=True, postorder=True, preorder=True)
        for x in postorder:
            level = 0
            for y in self.graph[x]:
                if self.weighted:
                    (y, d) = y
                if y == parents[x]:
                    continue
                (h, l) = self.bottom_hash[y]
                level = max(level, l + 1)
            ha = 1
            for y in self.graph[x]:
                if self.weighted:
                    (y, d) = y
                if y == parents[x]:
                    continue
                (h, l) = self.bottom_hash[y]
                ha *= h + self.hash_random_number[l]
                ha %= self.hash_mod
            self.bottom_hash[x] = (ha, level)
        if rerooting:
            self.top_hash = [None] * self.V
            self.top_hash[s] = (1, -1)
            for x in preorder:
                children = [y for (y, d) in self.graph[x] if y != parents[x]] if self.weighted else [y for y in self.graph[x] if y != parents[x]]
                if children:
                    l = len(children)
                    (l_lst, r_lst) = ([None] * (l + 1), [None] * (l + 1))
                    (l_lst[0], r_lst[l]) = ((1, -1), (1, -1))
                    for i in range(1, l + 1):
                        (h0, l0) = l_lst[i - 1]
                        (h1, l1) = self.bottom_hash[children[i - 1]]
                        l_lst[i] = (h0 * (h1 + self.hash_random_number[l1]) % self.hash_mod, max(l0, l1))
                    for i in range(l - 1, -1, -1):
                        (h0, l0) = r_lst[i + 1]
                        (h1, l1) = self.bottom_hash[children[i]]
                        r_lst[i] = (h0 * (h1 + self.hash_random_number[l1]) % self.hash_mod, max(l0, l1))
                    for i in range(l):
                        if x == s:
                            (ha, level) = (1, 0)
                        else:
                            (ha, level) = self.top_hash[x]
                        (h0, l0) = l_lst[i]
                        (h1, l1) = r_lst[i + 1]
                        ha *= h0 * h1
                        level = max(level, l0 + 1, l1 + 1)
                        ha += self.hash_random_number[level]
                        ha %= self.hash_mod
                        level += 1
                        self.top_hash[children[i]] = (ha, level)
        return

    def Hash(self, root, subtree=False):
        if subtree:
            (ha, level) = self.bottom_hash[root]
            ha += self.hash_random_number[level]
            ha %= self.hash_mod
        else:
            (h0, l0) = self.bottom_hash[root]
            (h1, l1) = self.top_hash[root]
            ha = (h0 * h1 + self.hash_random_number[max(l0, l1)]) % self.hash_mod
            level = max(l0, l1)
        return (ha, level)

    def Centroid(self, root=0):
        x = root
        (parents, size) = self.SIV_DFS(x, parents=True, subtree_size=True)
        while True:
            for y in self.graph[x]:
                if self.weighted:
                    (y, d) = y
                if y == parents[x]:
                    continue
                if size[y] * 2 > size[root]:
                    x = y
                    break
            else:
                for y in self.graph[x]:
                    if self.weighted:
                        (y, d) = y
                    if y == parents[x]:
                        continue
                    if size[root] <= 2 * size[y]:
                        return (x, y)
                return (x, None)

    def Centroid_Decomposition(self, edge=False, linked_point=False, point=False, tree=False):
        if edge:
            cd_edges_lst = [None] * self.V
        if linked_point:
            cd_linked_points = [None] * self.V
        if point:
            cd_points_lst = [None] * self.V
        if tree:
            cd_tree = [] * self.V
        edges = self.edges
        points = [i for i in range(self.V)]
        prev_centroid = None
        stack = [(edges, points, None, prev_centroid)] if linked_point else [(edges, points, prev_centroid)]
        while stack:
            if linked_point:
                (edges, points, lp, prev_centroid) = stack.pop()
            else:
                (edges, points, prev_centroid) = stack.pop()
            if len(points) == 1:
                centroid = points[0]
                if edge:
                    cd_edges_lst[centroid] = []
                if linked_point:
                    cd_linked_points[centroid] = lp
                if point:
                    cd_points_lst[centroid] = [centroid]
                if tree and prev_centroid != None:
                    cd_tree.append((prev_centroid, centroid))
                continue
            G = Graph(len(points), edges=edges, weighted=self.weighted)
            (centroid, _) = G.Centroid()
            if tree and prev_centroid != None:
                cd_tree.append((prev_centroid, points[centroid]))
            (parents, tour) = G.SIV_DFS(centroid, parents=True, preorder=True)
            dp = [None] * len(points)
            edges_lst = []
            points_lst = []
            if linked_point:
                linked_points = []
            for (i, x) in enumerate(G.graph[centroid]):
                if G.weighted:
                    (x, d) = x
                dp[x] = (i, 0)
                edges_lst.append([])
                points_lst.append([points[x]])
                if linked_point:
                    linked_points.append(points[x])
            for x in tour[1:]:
                for y in G.graph[x]:
                    if G.weighted:
                        (y, d) = y
                    if y == parents[x]:
                        continue
                    (i, j) = dp[x]
                    jj = len(points_lst[i])
                    edges_lst[i].append((j, jj, d) if G.weighted else (j, jj))
                    points_lst[i].append(points[y])
                    dp[y] = (i, jj)
            centroid = points[centroid]
            if edge:
                cd_edges_lst[centroid] = edges
            if linked_point:
                cd_linked_points[centroid] = lp
            if point:
                cd_points_lst[centroid] = points
            if linked_point:
                for (edges, points, lp) in zip(edges_lst, points_lst, linked_points):
                    stack.append((edges, points, lp, centroid))
            else:
                for (edges, points) in zip(edges_lst, points_lst):
                    stack.append((edges, points, centroid))
        retu = ()
        if edge:
            retu += (cd_edges_lst,)
        if linked_point:
            retu += (cd_linked_points,)
        if point:
            retu += (cd_points_lst,)
        if tree:
            retu += (cd_tree,)
        if len(retu) == 1:
            retu = retu[0]
        return retu

    def Bridges(self):
        (lowlink, preorder) = self.MIV_DFS(lowlink=True, preorder=True)
        order = [None] * self.V
        for x in range(self.V):
            order[preorder[x]] = x
        bridges = []
        for e in self.edges:
            if self.weighted:
                (x, y, d) = e
            else:
                (x, y) = e
            if order[x] < lowlink[y] or order[y] < lowlink[x]:
                bridges.append((x, y))
        return bridges

    def Articulation_Points(self):
        (lowlink, parents, preorder) = self.MIV_DFS(lowlink=True, parents=True, preorder=True)
        order = [None] * self.V
        for x in range(self.V):
            order[preorder[x]] = x
        articulation_points = []
        for x in range(self.V):
            if parents[x] == None:
                if len({y for y in self.graph[x] if parents[y] == x}) >= 2:
                    articulation_points.append(x)
            else:
                for y in self.graph[x]:
                    if parents[y] != x:
                        continue
                    if order[x] <= lowlink[y]:
                        articulation_points.append(x)
                        break
        return articulation_points

    def TECCD(self):
        (lowlink, preorder) = self.MIV_DFS(lowlink=True, preorder=True)
        order = [None] * self.V
        for x in range(self.V):
            order[preorder[x]] = x
        edges = []
        for e in self.edges:
            if self.weighted:
                (x, y, d) = e
            else:
                (x, y) = e
            if order[x] >= lowlink[y] and order[y] >= lowlink[x]:
                edges.append((x, y))
        teccd = Graph(self.V, edges=edges).MIV_DFS(linked_components=True)
        return teccd

    def LCD(self):
        points_lst = self.MIV_DFS(linked_components=True)
        edges_lst = [[] for i in range(len(points_lst))]
        idx = [None] * self.V
        for i in range(len(points_lst)):
            for j in range(len(points_lst[i])):
                idx[points_lst[i][j]] = (i, j)
        for tpl in self.edges:
            if self.weighted:
                (x, y, d) = tpl
            else:
                (x, y) = tpl
            (i, j0) = idx[x]
            (i, j1) = idx[y]
            if self.weighted:
                edges_lst[i].append((j0, j1, d))
            else:
                edges_lst[i].append((j0, j1))
        return (points_lst, edges_lst)

    def Dijkstra(self, s, route_restoration=False):
        dist = [self.inf] * self.V
        dist[s] = 0
        hq = [(0, s)]
        if route_restoration:
            parents = [None] * self.V
        while hq:
            (dx, x) = heapq.heappop(hq)
            if dist[x] < dx:
                continue
            for (y, dy) in self.graph[x]:
                if dist[y] > dx + dy:
                    dist[y] = dx + dy
                    if route_restoration:
                        parents[y] = x
                    heapq.heappush(hq, (dist[y], y))
        if route_restoration:
            return (dist, parents)
        else:
            return dist

    def Bellman_Ford(self, s, route_restoration=False):
        dist = [self.inf] * self.V
        dist[s] = 0
        if route_restoration:
            parents = [None] * self.V
        for _ in range(self.V - 1):
            for (i, j, d) in self.edges:
                if dist[j] > dist[i] + d:
                    dist[j] = dist[i] + d
                    if route_restoration:
                        parents[j] = i
                if not self.directed and dist[i] > dist[j] + d:
                    dist[i] = dist[j] + d
                    if route_restoration:
                        parents[i] = j
        negative_cycle = []
        for (i, j, d) in self.edges:
            if dist[j] > dist[i] + d:
                negative_cycle.append(j)
            if not self.directed and dist[i] > dist[j] + d:
                negative_cycle.append(i)
        if negative_cycle:
            is_negative_cycle = [False] * self.V
            for i in negative_cycle:
                if is_negative_cycle[i]:
                    continue
                else:
                    queue = [i]
                    is_negative_cycle[i] = True
                    while queue:
                        x = queue.popleft()
                        for (y, d) in self.graph[x]:
                            if not is_negative_cycle[y]:
                                queue.append(y)
                                is_negative_cycle[y] = True
                                if route_restoration:
                                    parents[y] = x
            for i in range(self.V):
                if is_negative_cycle[i]:
                    dist[i] = -self.inf
        if route_restoration:
            return (dist, parents)
        else:
            return dist

    def Warshall_Floyd(self, route_restoration=False):
        dist = [[self.inf] * self.V for i in range(self.V)]
        for i in range(self.V):
            dist[i][i] = 0
        if route_restoration:
            parents = [[j for j in range(self.V)] for i in range(self.V)]
        for (i, j, d) in self.edges:
            if i == j:
                continue
            if dist[i][j] > d:
                dist[i][j] = d
                if route_restoration:
                    parents[i][j] = i
            if not self.directed and dist[j][i] > d:
                dist[j][i] = d
                if route_restoration:
                    parents[j][i] = j
        for k in range(self.V):
            for i in range(self.V):
                for j in range(self.V):
                    if dist[i][j] > dist[i][k] + dist[k][j]:
                        dist[i][j] = dist[i][k] + dist[k][j]
                        if route_restoration:
                            parents[i][j] = parents[k][j]
        for i in range(self.V):
            if dist[i][i] < 0:
                for j in range(self.V):
                    if dist[i][j] != self.inf:
                        dist[i][j] = -self.inf
        if route_restoration:
            for i in range(self.V):
                if dist[i][i] == 0:
                    parents[i][i] = None
            return (dist, parents)
        else:
            return dist

    def Distance_Frequency(self):
        mod = 206158430209
        cnt = [0] * N
        (cd_edges, cd_points, cd_tree) = self.Centroid_Decomposition(edge=True, point=True, tree=True)
        CD = Graph(N, edges=cd_tree)
        (parents, tour) = CD.SIV_DFS(cd_tree[0][0], parents=True, postorder=True)
        for x in tour:
            C = [0] * (len(cd_points[x]) + 1)
            for y in CD.graph[x]:
                if y == parents[x]:
                    continue
                depth = Graph(len(cd_points[y]), edges=cd_edges[y], weighted=self.weighted).SIV_DFS(0, unweighted_dist=True)
                CC = [0] * (max(depth) + 2)
                for d in depth:
                    CC[d + 1] += 1
                    cnt[d + 1] += 2
                    C[d + 1] += 1
                poly = NTT_Pow(CC, 2)
                for (d, c) in enumerate(poly):
                    if d < N:
                        cnt[d] -= c
            while C and C[-1] == 0:
                C.pop()
            poly = NTT_Pow(C, 2)
            for (d, c) in enumerate(poly):
                if d < N:
                    cnt[d] += c
        for i in range(N):
            cnt[i] //= 2
        return cnt

    def Shortest_Path_Count(self, s, mod=0, weighted=False):
        if weighted:
            dist = self.Dijkstra(s)
        else:
            dist = self.SIV_BFS(s, unweighted_dist=True)
        cnt = [0] * self.V
        cnt[s] = 1
        for x in sorted([x for x in range(self.V)], key=lambda x: dist[x]):
            for y in self.graph[x]:
                if self.weighted:
                    (y, d) = y
                else:
                    d = 1
                if dist[x] + d == dist[y]:
                    cnt[y] += cnt[x]
                    if mod:
                        cnt[y] %= mod
        return cnt

    def K_Shortest_Path_Routing(self, s, t, K, edge_unicursal=False, point_unicursal=False):
        if point_unicursal:
            (dist, parents) = self.Dijkstra(s, route_restoration=True)
            route = tuple(self.Route_Restoration(s, t, parents))
            queue = [(dist[t], route, [dist[x] for x in route])]
            set_queue = set()
            set_queue.add(route)
            retu = []
            while queue and K:
                (d, route, route_dist) = heapq.heappop(queue)
                retu.append((d, route, route_dist))
                K -= 1
                set_route = set()
                for i in range(len(route) - 1):
                    x = route[i]
                    set_route.add(x)
                    edges = [(v, u, d) for (u, v, d) in self.edges if not u in set_route and (not v in set_route)]
                    G_rev = Graph(self.V, edges=edges, directed=self.directed, weighted=self.weighted, inf=self.inf)
                    (dist_rev, parents_rev) = G_rev.Dijkstra(t, route_restoration=True)
                    for (y, d) in self.graph[x]:
                        if y == route[i + 1]:
                            continue
                        if dist_rev[y] == self.inf:
                            continue
                        tpl = route[:i + 1] + tuple(self.Route_Restoration(t, y, parents_rev, reverse=True))
                        if not tpl in set_queue:
                            heapq.heappush(queue, (route_dist[i] + d + dist_rev[y], tpl, route_dist[:i + 1] + [route_dist[i] + d + dist_rev[y] - dist_rev[z] for z in tpl[i + 1:]]))
                            set_queue.add(tpl)
        elif edge_unicursal:
            (dist, parents) = self.Dijkstra(s, route_restoration=True)
            route = tuple(self.Route_Restoration(s, t, parents))
            queue = [(dist[t], route, [dist[x] for x in route])]
            set_queue = set()
            set_queue.add(route)
            retu = []
            while queue and K:
                (d, route, route_dist) = heapq.heappop(queue)
                retu.append((d, route, route_dist))
                K -= 1
                set_route = set()
                for i in range(len(route) - 1):
                    x = route[i]
                    y = route[i + 1]
                    set_route.add((x, y, route_dist[i + 1] - route_dist[i]))
                    if not self.directed:
                        set_route.add((y, x, route_dist[i + 1] - route_dist[i]))
                    edges = [(v, u, d) for (u, v, d) in self.edges if not (u, v, d) in set_route]
                    G_rev = Graph(self.V, edges=edges, directed=self.directed, weighted=self.weighted, inf=self.inf)
                    (dist_rev, parents_rev) = G_rev.Dijkstra(t, route_restoration=True)
                    for (y, d) in self.graph[x]:
                        if y == route[i + 1]:
                            continue
                        if dist_rev[y] == self.inf:
                            continue
                        tpl = route[:i + 1] + tuple(self.Route_Restoration(t, y, parents_rev, reverse=True))
                        if not tpl in set_queue:
                            heapq.heappush(queue, (route_dist[i] + d + dist_rev[y], tpl, route_dist[:i + 1] + [route_dist[i] + d + dist_rev[y] - dist_rev[z] for z in tpl[i + 1:]]))
                            set_queue.add(tpl)
        else:
            (dist, parents) = self.Dijkstra(s, route_restoration=True)
            if dist[t] == self.inf:
                return False
            route_lst = [tuple(self.Route_Restoration(s, x, parents)) for x in range(self.V)]
            edges_rev = [(j, i, d) for (i, j, d) in self.edges]
            G_rev = Graph(self.V, edges=edges_rev, weighted=self.weighted, directed=self.directed, inf=self.inf)
            (dist_rev, parents_rev) = G_rev.Dijkstra(t, route_restoration=True)
            route_rev_lst = []
            for x in range(self.V):
                route_rev_lst.append(tuple(self.Route_Restoration(t, x, parents_rev, reverse=True)))
            route = route_lst[t]
            queue = [(dist[t], route, [dist[x] for x in route])]
            set_queue = set()
            set_queue.add(route)
            retu = []
            while queue and K:
                (d, route, route_dist) = heapq.heappop(queue)
                retu.append((d, route, route_dist))
                K -= 1
                for i in range(len(route)):
                    x = route[i]
                    for (y, d) in self.graph[x]:
                        if i != len(route) - 1 and y == route[i + 1]:
                            continue
                        tpl = route[:i + 1] + route_rev_lst[y]
                        if not tpl in set_queue:
                            heapq.heappush(queue, (route_dist[i] + d + dist_rev[y], tpl, route_dist[:i + 1] + [route_dist[i] + d + dist_rev[y] - dist_rev[z] for z in route_rev_lst[y]]))
                            set_queue.add(tpl)
        return retu

    def Route_Restoration(self, s, g, parents):
        route = [g]
        while s != g:
            if parents[g] == None:
                route = []
                break
            g = parents[g]
            route.append(g)
        route = route[::-1]
        return route

    def Negative_Cycls(self):
        dist = [0] * self.V
        for _ in range(self.V - 1):
            for (i, j, d) in self.edges:
                dist[j] = min(dist[j], dist[i] + d)
        for (i, j, d) in self.edges:
            if dist[j] > dist[i] + d:
                return True
        return False

    def Kruskal(self, maximize=False):
        UF = UnionFind(self.V)
        sorted_edges = sorted(self.edges, key=lambda x: x[2], reverse=maximize)
        spnning_tree = []
        for (i, j, d) in sorted_edges:
            if not UF.Same(i, j):
                UF.Union(i, j)
                spnning_tree.append((i, j, d))
        return spnning_tree

    def Max_Clique(self):
        graph = [[False] * self.V for x in range(self.V)]
        for x in range(self.V):
            for y in self.graph[x]:
                if self.weighted:
                    (y, d) = y
                graph[x][y] = True
        (N0, N1) = (self.V // 2, self.V - self.V // 2)
        pop_count = [sum((bit >> i & 1 for i in range(N1))) for bit in range(1 << N1)]
        is_clique0 = [True] * (1 << N0)
        for j in range(N0):
            for i in range(j):
                if not graph[i][j]:
                    is_clique0[1 << i | 1 << j] = False
        for i in range(N0):
            for bit in range(1 << N0):
                if bit & 1 << i:
                    is_clique0[bit] = is_clique0[bit] & is_clique0[bit ^ 1 << i]
        is_clique1 = [True] * (1 << N1)
        for j in range(N1):
            for i in range(j):
                if not graph[i + N0][j + N0]:
                    is_clique1[1 << i | 1 << j] = False
        for i in range(N1):
            for bit in range(1 << N1):
                if bit & 1 << i:
                    is_clique1[bit] = is_clique1[bit] & is_clique1[bit ^ 1 << i]
        max_clique_bit = [bit if is_clique0[bit] else 0 for bit in range(1 << N0)]
        for i in range(N0):
            for bit in range(1 << N0):
                if bit & 1 << i and pop_count[max_clique_bit[bit]] < pop_count[max_clique_bit[bit ^ 1 << i]]:
                    max_clique_bit[bit] = max_clique_bit[bit ^ 1 << i]
        dp = [(1 << N0) - 1] * (1 << N1)
        for j in range(N1):
            for i in range(N0):
                if not graph[j + N0][i]:
                    dp[1 << j] ^= 1 << i
        for i in range(N1):
            for bit in range(1 << N1):
                if bit & 1 << i:
                    dp[bit] &= dp[bit ^ 1 << i]
        (bit0, bit1) = (0, 0)
        for bit in range(1 << N1):
            if is_clique1[bit] and pop_count[max_clique_bit[dp[bit]]] + pop_count[bit] > pop_count[bit0] + pop_count[bit1]:
                bit0 = max_clique_bit[dp[bit]]
                bit1 = bit
        max_clique = [i for i in range(N0) if bit0 & 1 << i] + [i + N0 for i in range(N1) if bit1 & 1 << i]
        return max_clique

    def Cliques(self):
        graph = [[False] * self.V for x in range(self.V)]
        for x in range(self.V):
            for y in self.graph[x]:
                if self.weighted:
                    (y, d) = y
                graph[x][y] = True
        cliques = []
        points = [x for x in range(self.V)]
        while points:
            l = len(points)
            (min_degree, min_degree_point) = (self.inf, None)
            sum_degree = 0
            for x in points:
                s = sum((graph[x][y] for y in points))
                sum_degree += s
                if s < min_degree:
                    min_degree = s
                    min_degree_point = x
            if min_degree ** 2 >= sum_degree:
                lst = points
            else:
                lst = [x for x in points if x == min_degree_point or graph[min_degree_point][x]]
            l = len(lst)
            is_clique = [True] * (1 << l)
            for j in range(l):
                for i in range(j):
                    if not graph[lst[i]][lst[j]]:
                        is_clique[1 << i | 1 << j] = False
            for i in range(l):
                for bit in range(1 << l):
                    if bit & 1 << i:
                        is_clique[bit] = is_clique[bit] & is_clique[bit ^ 1 << i]
            if min_degree ** 2 >= sum_degree:
                for bit in range(1 << l):
                    if is_clique[bit]:
                        cliques.append([lst[i] for i in range(l) if bit & 1 << i])
            else:
                idx = lst.index(min_degree_point)
                for bit in range(1 << l):
                    if is_clique[bit] and bit & 1 << idx:
                        cliques.append([lst[i] for i in range(l) if bit & 1 << i])
            if min_degree ** 2 >= sum_degree:
                points = []
            else:
                points = [x for x in points if x != min_degree_point]
        return cliques

    def Ford_Fulkerson(self, s, t):
        max_flow = 0
        residual_graph = [defaultdict(int) for i in range(self.V)]
        if self.weighted:
            for (i, j, d) in self.edges:
                if not d:
                    continue
                residual_graph[i][j] += d
                if not self.directed:
                    residual_graph[j][i] += d
        else:
            for (i, j) in self.edges:
                residual_graph[i][j] += 1
                if not self.directed:
                    residual_graph[j][i] += 1
        while True:
            parents = [None] * self.V
            parents[s] = s
            seen = [False] * self.V
            seen[s] = True
            queue = deque([s])
            while queue:
                x = queue.popleft()
                for y in residual_graph[x].keys():
                    if not seen[y]:
                        seen[y] = True
                        queue.append(y)
                        parents[y] = x
                        if y == t:
                            tt = t
                            while tt != s:
                                residual_graph[parents[tt]][tt] -= 1
                                residual_graph[tt][parents[tt]] += 1
                                if not residual_graph[parents[tt]][tt]:
                                    residual_graph[parents[tt]].pop(tt)
                                tt = parents[tt]
                            max_flow += 1
                            break
                else:
                    continue
                break
            else:
                break
        return max_flow

    def BFS(self, s):
        seen = [False] * self.V
        seen[s] = True
        queue = deque([s])
        while queue:
            x = queue.popleft()
            for y in self.graph[x]:
                if self.weighted:
                    (y, d) = y
                if not seen[y]:
                    seen[y] = True
                    queue.append(y)
        return

    def DFS(self, s):
        seen = [False] * self.V
        finished = [False] * self.V
        stack = [(s, 0)] if self.weighted else [s]
        while stack:
            if self.weighted:
                (x, d) = stack.pop()
            else:
                x = stack.pop()
            if not seen[x]:
                seen[x] = True
                stack.append((x, d) if self.weighted else x)
                for y in self.graph[x]:
                    if self.weighted:
                        (y, d) = y
                    if not seen[y]:
                        stack.append((y, d) if self.weighted else y)
            elif not finished[x]:
                finished[x] = True
        return

    def Euler_Path(self, s=None, t=None):
        if self.directed:
            indegree = [0] * self.V
            outdegree = [0] * self.V
            graph = [[] for x in range(self.V)]
            for tpl in self.edges:
                if self.weighted:
                    (u, v, d) = tpl
                else:
                    (u, v) = tpl
                indegree[v] += 1
                outdegree[u] += 1
                graph[v].append(u)
            for x in range(self.V):
                if indegree[x] + 1 == outdegree[x]:
                    if s == None:
                        s = x
                    elif s != x:
                        return False
                elif indegree[x] == outdegree[x] + 1:
                    if t == None:
                        t = x
                    elif t != x:
                        return False
                elif indegree[x] != outdegree[x]:
                    return False
            if (s, t) == (None, None):
                for x in range(self.V):
                    if graph[x]:
                        s = x
                        t = x
                        break
            elif s == None:
                s = t
            elif t == None:
                t = s
            elif s == t:
                for x in range(self.V):
                    if indegree[x] != outdegree[x]:
                        return False
            queue = [t]
            euler_path = []
            while queue:
                while graph[queue[-1]]:
                    queue.append(graph[queue[-1]].pop())
                x = queue.pop()
                euler_path.append(x)
            for x in range(self.V):
                if graph[x]:
                    return False
        else:
            degree = [0] * self.V
            graph = [[] for x in range(self.V)]
            use_count = [defaultdict(int) for x in range(self.V)]
            for tpl in self.edges:
                if self.weighted:
                    (u, v, d) = tpl
                else:
                    (u, v) = tpl
                degree[v] += 1
                degree[u] += 1
                graph[u].append(v)
                graph[v].append(u)
            for x in range(self.V):
                if degree[x] % 2:
                    if s == None and t != x:
                        s = x
                    elif t == None and s != x:
                        t = x
                    elif not x in (s, t):
                        return False
            if s == None and t == None:
                for x in range(self.V):
                    if graph[x]:
                        s = x
                        t = x
                        break
                else:
                    (s, t) = (0, 0)
            elif s == None:
                s = t
            elif t == None:
                t = s
            elif s != t:
                if degree[s] % 2 == 0 or degree[t] % 2 == 0:
                    return False
            queue = [t]
            euler_path = []
            while queue:
                while graph[queue[-1]]:
                    if use_count[queue[-1]][graph[queue[-1]][-1]]:
                        use_count[queue[-1]][graph[queue[-1]][-1]] -= 1
                        graph[queue[-1]].pop()
                    else:
                        queue.append(graph[queue[-1]].pop())
                        use_count[queue[-1]][queue[-2]] += 1
                x = queue.pop()
                euler_path.append(x)
            for x in range(self.V):
                if graph[x]:
                    return False
        if euler_path[0] != s:
            return False
        return euler_path

class Segment_Tree:

    def __init__(self, N, f, e, lst=None):
        self.f = f
        self.e = e
        self.N = N
        if lst == None:
            self.segment_tree = [self.e] * 2 * self.N
        else:
            assert len(lst) <= self.N
            self.segment_tree = [self.e] * self.N + [x for x in lst] + [self.e] * (N - len(lst))
            for i in range(self.N - 1, 0, -1):
                self.segment_tree[i] = self.f(self.segment_tree[i << 1], self.segment_tree[i << 1 | 1])

    def __getitem__(self, i):
        if type(i) == int:
            if -self.N <= i < 0:
                return self.segment_tree[i + self.N * 2]
            elif 0 <= i < self.N:
                return self.segment_tree[i + self.N]
            else:
                raise IndexError('list index out of range')
        else:
            (a, b, c) = (i.start, i.stop, i.step)
            if a == None:
                a = self.N
            else:
                a += self.N
            if b == None:
                b = self.N * 2
            else:
                b += self.N
            return self.segment_tree[slice(a, b, c)]

    def __setitem__(self, i, x):
        if -self.N <= i < 0:
            i += self.N * 2
        elif 0 <= i < self.N:
            i += self.N
        else:
            raise IndexError('list index out of range')
        self.segment_tree[i] = x
        while i > 1:
            i >>= 1
            self.segment_tree[i] = self.f(self.segment_tree[i << 1], self.segment_tree[i << 1 | 1])

    def Build(self, lst):
        for (i, x) in enumerate(lst, self.N):
            self.segment_tree[i] = x
        for i in range(self.N - 1, 0, -1):
            self.segment_tree[i] = self.f(self.segment_tree[i << 1], self.segment_tree[i << 1 | 1])

    def Fold(self, L=None, R=None):
        if L == None:
            L = self.N
        else:
            L += self.N
        if R == None:
            R = self.N * 2
        else:
            R += self.N
        vL = self.e
        vR = self.e
        while L < R:
            if L & 1:
                vL = self.f(vL, self.segment_tree[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.segment_tree[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)

    def Fold_Index(self, L=None, R=None):
        if L == None:
            L = self.N
        else:
            L += self.N
        if R == None:
            R = self.N * 2
        else:
            R += self.N
        if L == R:
            return None
        x = self.Fold(L - self.N, R - self.N)
        while L < R:
            if L & 1:
                if self.segment_tree[L] == x:
                    i = L
                    break
                L += 1
            if R & 1:
                R -= 1
                if self.segment_tree[R] == x:
                    i = R
                    break
            L >>= 1
            R >>= 1
        while i < self.N:
            if self.segment_tree[i] == self.segment_tree[i << 1]:
                i <<= 1
            else:
                i <<= 1
                i |= 1
        i -= self.N
        return i

    def Bisect_Right(self, L=None, f=None):
        if L == self.N:
            return self.N
        if L == None:
            L = 0
        L += self.N
        vl = self.e
        vr = self.e
        (l, r) = (L, self.N * 2)
        while l < r:
            if l & 1:
                vl = self.f(vl, self.segment_tree[l])
                l += 1
            if r & 1:
                r -= 1
                vr = self.f(self.segment_tree[r], vr)
            l >>= 1
            r >>= 1
        if f(self.f(vl, vr)):
            return self.N
        v = self.e
        while True:
            while L % 2 == 0:
                L >>= 1
            vv = self.f(v, self.segment_tree[L])
            if f(vv):
                v = vv
                L += 1
            else:
                while L < self.N:
                    L <<= 1
                    vv = self.f(v, self.segment_tree[L])
                    if f(vv):
                        v = vv
                        L += 1
                return L - self.N

    def Bisect_Left(self, R=None, f=None):
        if R == 0:
            return 0
        if R == None:
            R = self.N
        R += self.N
        vl = self.e
        vr = self.e
        (l, r) = (self.N, R)
        while l < r:
            if l & 1:
                vl = self.f(vl, self.segment_tree[l])
                l += 1
            if r & 1:
                r -= 1
                vr = self.f(self.segment_tree[r], vr)
            l >>= 1
            r >>= 1
        if f(self.f(vl, vr)):
            return 0
        v = self.e
        while True:
            R -= 1
            while R > 1 and R % 2:
                R >>= 1
            vv = self.f(self.segment_tree[R], v)
            if f(vv):
                v = vv
            else:
                while R < self.N:
                    R = 2 * R + 1
                    vv = self.f(self.segment_tree[R], v)
                    if f(vv):
                        v = vv
                        R -= 1
                return R + 1 - self.N

    def __str__(self):
        return '[' + ', '.join(map(str, self.segment_tree[self.N:])) + ']'
(N, M) = map(int, readline().split())
edges = []
P = list(map(int, readline().split()))
for i in range(1, N):
    edges.append((i, P[i - 1] - 1))
G = Graph(N, edges=edges)
(tour, parents, depth) = G.SIV_DFS(0, euler_tour=True, parents=True, unweighted_dist=True)
in_index = [None] * N
out_index = [None] * N
for (i, x) in enumerate(tour):
    if x >= 0:
        in_index[x] = i
    else:
        out_index[~x] = i
inf = 1 << 30
IN = Segment_Tree(N, min, inf, in_index)
OUT = Segment_Tree(N, max, -inf, out_index)
ST = Segment_Tree(2 * N, min, inf, [depth[x] if x >= 0 else depth[parents[~x]] for x in tour[:-1]] + [-1])
for _ in range(M):
    (l, r) = map(int, readline().split())
    l -= 1
    mi = IN.Fold(l, r)
    ma = OUT.Fold(l, r)
    (ans, d) = (None, -1)
    for x in (tour[mi], ~tour[ma]):
        mi = min(IN.Fold(l, x), IN.Fold(x + 1, r))
        ma = max(OUT.Fold(l, x), OUT.Fold(x + 1, r))
        dd = ST.Fold(mi, ma)
        if d < dd:
            d = dd
            ans = x
    print(ans + 1, d)

Solution (Python):
import os, sys, random, threading
from random import randint
from copy import deepcopy
from io import BytesIO, IOBase
from types import GeneratorType
from functools import lru_cache, reduce
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from itertools import accumulate, combinations, permutations
from heapq import heapify, heappop, heappush
from typing import Generic, Iterable, Iterator, TypeVar, Union, List
from string import ascii_lowercase, ascii_uppercase
from math import ceil, floor, sqrt, pi, factorial, gcd, log, log10, log2, inf
from decimal import Decimal, getcontext
BUFSIZE = 4096

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
sys.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper(sys.stdout)
mod = int(1000000000.0 + 7)
inf = int(1e+20)
input = lambda : sys.stdin.readline().rstrip('\r\n')
MI = lambda : map(int, input().split())
li = lambda : list(MI())
ii = lambda : int(input())
py = lambda : print('YES')
pn = lambda : print('NO')
DIRS = [(0, 1), (1, 0), (0, -1), (-1, 0)]
DIRS8 = [(0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1), (-1, 0), (-1, 1)]

class HLD:

    def __init__(self, g, root):
        n = len(g)
        self.g = g
        self.fa = [0] * (n + 5)
        self.size = [1] * (n + 5)
        self.dep = [0] * (n + 5)
        self.son = [0] * (n + 5)
        self.dfn = [0] * (n + 5)
        self.top = [0] * (n + 5)
        self.rank = [0] * (n + 5)
        fa = self.fa
        size = self.size
        dep = self.dep
        son = self.son
        dfn = self.dfn
        top = self.top
        rank = self.rank
        stk = [[root, 0, 0]]
        dep[root] = 1
        while stk:
            (u, flag, father) = stk.pop()
            if flag:
                for v in g[u]:
                    if v != father:
                        size[u] += size[v]
                        if son[u] == 0 or size[v] > size[son[u]]:
                            son[u] = v
            else:
                stk.append([u, 1, father])
                for v in g[u]:
                    if v != father:
                        stk.append([v, 0, u])
                        fa[v] = u
                        dep[v] = dep[u] + 1
        stk = [[root, root]]
        tot = 1
        while stk:
            (u, tops) = stk.pop()
            dfn[u] = tot
            rank[tot] = u
            tot += 1
            top[u] = tops
            if son[u] == 0:
                continue
            for v in g[u]:
                if v != fa[u] and v != son[u]:
                    stk.append([v, v])
            stk.append([son[u], tops])

    def kth_fa(self, root, k):
        fa = self.fa
        size = self.size
        dep = self.dep
        son = self.son
        dfn = self.dfn
        top = self.top
        rank = self.rank
        if k >= dep[root]:
            return -1
        while True:
            u = top[root]
            if dfn[root] - k >= dfn[u]:
                return rank[dfn[root] - k]
            k -= dfn[root] - dfn[u] + 1
            root = fa[u]

    def lca(self, u, v):
        fa = self.fa
        size = self.size
        dep = self.dep
        son = self.son
        dfn = self.dfn
        top = self.top
        rank = self.rank
        while top[u] != top[v]:
            if dep[top[u]] > dep[top[v]]:
                u = fa[top[u]]
            else:
                v = fa[top[v]]
        return v if dep[u] > dep[v] else u

class SparseTable:

    def __init__(self, data: list, func=gcd):
        self.func = func
        self.st = st = [list(data)]
        (i, N) = (1, len(st[0]))
        while 2 * i <= N + 1:
            qz = st[-1]
            st.append([func(qz[j], qz[j + i]) for j in range(N - 2 * i + 1)])
            i <<= 1

    def query(self, begin: int, end: int):
        lg = (end - begin + 1).bit_length() - 1
        return self.func(self.st[lg][begin], self.st[lg][end - (1 << lg) + 1])
(n, q) = li()
g = [[] for _ in range(n + 1)]
for (u, fa) in enumerate(li(), 2):
    g[fa].append(u)
hld = HLD(g, 1)
dfn = hld.dfn
rank = hld.rank
dep = hld.dep
maxdfn = SparseTable(dfn, max)
mindfn = SparseTable(dfn, min)

def op(u, v):
    return hld.lca(u, v)
stlca = SparseTable(list(range(n + 1)), op)

def check(u, v, delt):
    if u == delt:
        return dep[stlca.query(u + 1, v)]
    if v == delt:
        return dep[stlca.query(u, v - 1)]
    l = stlca.query(u, delt - 1)
    r = stlca.query(delt + 1, v)
    return dep[hld.lca(l, r)]
for _ in range(q):
    (u, v) = li()
    if u + 1 == v:
        if dep[u] > dep[v]:
            print(v, dep[u] - 1)
        else:
            print(u, dep[v] - 1)
    else:
        mx = maxdfn.query(u, v)
        mi = mindfn.query(u, v)
        mxdep = check(u, v, rank[mx])
        midep = check(u, v, rank[mi])
        if midep > mxdep:
            print(rank[mi], midep - 1)
        else:
            print(rank[mx], mxdep - 1)