code: def query(self, u, v):
          
          # -- assume w.l.o.g. that v is not higher than u in the tree
          if self.level[u] > self.level[v]:
              u, v = v, u
          # -- put v at the same level as u
          depth = len(self.anc)
          for k in range(depth-1, -1, -1):
              if self.level[u] <= self.level[v] - (1 << k):
                  v = self.anc[k][v]
          assert self.level[u] == self.level[v]
          if u == v:
              return u
          # -- climb until the lowest common ancestor
          for k in range(depth-1, -1, -1):
              if self.anc[k][u] != self.anc[k][v]:
                  u = self.anc[k][u]
                  v = self.anc[k][v]
          assert self.anc[0][u] == self.anc[0][v]
          return self.anc[0][u]
docs: :returns: the lowest common ancestor of u and v
          :complexity: O(log n)