# Path: tryalgo/range_minimum_query.py
# class RangeMinQuery:
#     """Range minimum query
# 
#     maintains a table t, can read/write items t[i],
#     and query range_min(i,k) = min{ t[i], t[i + 1], ..., t[k - 1]}
#     :complexity: all operations in O(log n), for n = len(t)
#     """
#     def __init__(self, t, INF=float('inf')):
#         self.INF = INF
#         self.N = 1
#         while self.N < len(t):                     # find size N
#             self.N *= 2
#         self.s = [self.INF] * (2 * self.N)
#         for i in range(len(t)):                    # store values of t
#             self.s[self.N + i] = t[i]              # in the leaf nodes
#         for p in range(self.N - 1, 0, -1):         # fill inner nodes
#             self.s[p] = min(self.s[2 * p], self.s[2 * p + 1])
# 
#     def __getitem__(self, i):
#         return self.s[self.N + i]
# 
#     def __setitem__(self, i, v):
#         """ sets t[i] to v.
#             :complexity: O(log len(t))
#         """
#         p = self.N + i
#         self.s[p] = v
#         p //= 2                                    # climb up the tree
#         while p > 0:                               # update node
#             self.s[p] = min(self.s[2 * p], self.s[2 * p + 1])
#             p //= 2
# 
#     def range_min(self, i, k):
#         """:returns:  min{ t[i], t[i + 1], ..., t[k - 1]}
#         :complexity: O(log len(t))
#         """
#         return self._range_min(1, 0, self.N, i, k)
# 
#     def _range_min(self, p, start, span, i, k):
#         """returns the minimum in t in the indexes [i, k) intersected
#            with [start, start + span).
#            p is the node associated to the later interval.
#         """
#         if start + span <= i or k <= start:        # disjoint intervals
#             return self.INF
#         if i <= start and start + span <= k:       # contained intervals
#             return self.s[p]
#         left = self._range_min(2 * p, start, span // 2,
#                                i, k)
#         right = self._range_min(2 * p + 1, start + span // 2, span // 2,
#                                 i, k)
#         return min(left, right)


from tryalgo.range_minimum_query import RangeMinQuery

# snip{ lowest_common_ancestor_by_rmq
class LowestCommonAncestorRMQ:
    """Lowest common ancestor data structure using a reduction to
       range minimum query
    """
    def __init__(self, graph):
        """builds the structure from a given tree

        :param graph: adjacency matrix of a tree
        :complexity: O(n log n), with n = len(graph)
        """
        n = len(graph)
        dfs_trace = []
        self.last = [None] * n
        to_visit = [(0, 0, None)]            # node 0 is root
        succ = [0] * n
        while to_visit:
            level, node, father = to_visit[-1]
            self.last[node] = len(dfs_trace)
            dfs_trace.append((level, node))
            if succ[node] < len(graph[node]) and \
               graph[node][succ[node]] == father:
                succ[node] += 1
            if succ[node] == len(graph[node]):
                to_visit.pop()
            else:
                neighbor = graph[node][succ[node]]
                succ[node] += 1
                to_visit.append((level + 1, neighbor, node))

# Path: tryalgo/range_minimum_query.py
# class RangeMinQuery:
#     """Range minimum query
# 
#     maintains a table t, can read/write items t[i],
#     and query range_min(i,k) = min{ t[i], t[i + 1], ..., t[k - 1]}
#     :complexity: all operations in O(log n), for n = len(t)
#     """
#     def __init__(self, t, INF=float('inf')):
#         self.INF = INF
#         self.N = 1
#         while self.N < len(t):                     # find size N
#             self.N *= 2
#         self.s = [self.INF] * (2 * self.N)
#         for i in range(len(t)):                    # store values of t
#             self.s[self.N + i] = t[i]              # in the leaf nodes
#         for p in range(self.N - 1, 0, -1):         # fill inner nodes
#             self.s[p] = min(self.s[2 * p], self.s[2 * p + 1])
# 
#     def __getitem__(self, i):
#         return self.s[self.N + i]
# 
#     def __setitem__(self, i, v):
#         """ sets t[i] to v.
#             :complexity: O(log len(t))
#         """
#         p = self.N + i
#         self.s[p] = v
#         p //= 2                                    # climb up the tree
#         while p > 0:                               # update node
#             self.s[p] = min(self.s[2 * p], self.s[2 * p + 1])
#             p //= 2
# 
#     def range_min(self, i, k):
#         """:returns:  min{ t[i], t[i + 1], ..., t[k - 1]}
#         :complexity: O(log len(t))
#         """
#         return self._range_min(1, 0, self.N, i, k)
# 
#     def _range_min(self, p, start, span, i, k):
#         """returns the minimum in t in the indexes [i, k) intersected
#            with [start, start + span).
#            p is the node associated to the later interval.
#         """
#         if start + span <= i or k <= start:        # disjoint intervals
#             return self.INF
#         if i <= start and start + span <= k:       # contained intervals
#             return self.s[p]
#         left = self._range_min(2 * p, start, span // 2,
#                                i, k)
#         right = self._range_min(2 * p + 1, start + span // 2, span // 2,
#                                 i, k)
#         return min(left, right)


# Path: tryalgo/lowest_common_ancestor.py
from tryalgo.range_minimum_query import RangeMinQuery


# snip{ lowest_common_ancestor_by_rmq
class LowestCommonAncestorRMQ:
    """Lowest common ancestor data structure using a reduction to
       range minimum query
    """
    def __init__(self, graph):
        """builds the structure from a given tree

        :param graph: adjacency matrix of a tree
        :complexity: O(n log n), with n = len(graph)
        """
        n = len(graph)
        dfs_trace = []
        self.last = [None] * n
        to_visit = [(0, 0, None)]            # node 0 is root
        succ = [0] * n
        while to_visit:
            level, node, father = to_visit[-1]
            self.last[node] = len(dfs_trace)
            dfs_trace.append((level, node))
            if succ[node] < len(graph[node]) and \
               graph[node][succ[node]] == father:
                succ[node] += 1
            if succ[node] == len(graph[node]):
                to_visit.pop()
            else:
                neighbor = graph[node][succ[node]]
                succ[node] += 1
                to_visit.append((level + 1, neighbor, node))

        self.rmq = RangeMinQuery(dfs_trace, (float('inf'), None))