class _BNode():
    __slots__ = ["tree", "contents", "children"]

    def __init__(self, tree, contents=None, children=None):
        self.tree = tree
        self.contents = contents or []
        self.children = children or []
        if self.children:
            assert len(self.contents) + 1 == len(self.children), \
                "one more child than data item required"

    def __repr__(self):
        name = getattr(self, "children", 0) and "Branch" or "Leaf"
        return "<%s %s>" % (name, ", ".join(map(str, self.contents)))

    def lateral(self, parent, parent_index, dest, dest_index):
        if parent_index > dest_index:
            dest.contents.append(parent.contents[dest_index])
            parent.contents[dest_index] = self.contents.pop(0)
            if self.children:
                dest.children.append(self.children.pop(0))
        else:
            dest.contents.insert(0, parent.contents[parent_index])
            parent.contents[parent_index] = self.contents.pop()
            if self.children:
                dest.children.insert(0, self.children.pop())

    def shrink(self, ancestors):
        parent = None

        if ancestors:
            parent, parent_index = ancestors.pop()
            # try to lend to the left neighboring sibling
            if parent_index:
                left_sib = parent.children[parent_index - 1]
                if len(left_sib.contents) < self.tree.order:
                    self.lateral(
                        parent, parent_index, left_sib, parent_index - 1)
                    return

            # try the right neighbor
            if parent_index + 1 < len(parent.children):
                right_sib = parent.children[parent_index + 1]
                if len(right_sib.contents) < self.tree.order:
                    self.lateral(
                        parent, parent_index, right_sib, parent_index + 1)
                    return

        center = len(self.contents) // 2
        sibling, push = self.split()

        if not parent:
            parent, parent_index = self.tree.BRANCH(
                self.tree, children=[self]), 0
            self.tree._root = parent

        # pass the median up to the parent
        parent.contents.insert(parent_index, push)
        parent.children.insert(parent_index + 1, sibling)
        if len(parent.contents) > parent.tree.order:
            parent.shrink(ancestors)

    def grow(self, ancestors):
        parent, parent_index = ancestors.pop()

        minimum = self.tree.order // 2
        left_sib = right_sib = None

        # try to borrow from the right sibling
        if parent_index + 1 < len(parent.children):
            right_sib = parent.children[parent_index + 1]
            if len(right_sib.contents) > minimum:
                right_sib.lateral(parent, parent_index + 1, self, parent_index)
                return

        # try to borrow from the left sibling
        if parent_index:
            left_sib = parent.children[parent_index - 1]
            if len(left_sib.contents) > minimum:
                left_sib.lateral(parent, parent_index - 1, self, parent_index)
                return

        # consolidate with a sibling - try left first
        if left_sib:
            left_sib.contents.append(parent.contents[parent_index - 1])
            left_sib.contents.extend(self.contents)
            if self.children:
                left_sib.children.extend(self.children)
            parent.contents.pop(parent_index - 1)
            parent.children.pop(parent_index)
        else:
            self.contents.append(parent.contents[parent_index])
            self.contents.extend(right_sib.contents)
            if self.children:
                self.children.extend(right_sib.children)
            parent.contents.pop(parent_index)
            parent.children.pop(parent_index + 1)

        if len(parent.contents) < minimum:
            if ancestors:
                # parent is not the root
                parent.grow(ancestors)
            elif not parent.contents:
                # parent is root, and its now empty
                self.tree._root = left_sib or self

    def split(self):
        center = len(self.contents) // 2
        median = self.contents[center]
        sibling = type(self)(
            self.tree,
            self.contents[center + 1:],
            self.children[center + 1:])
        self.contents = self.contents[:center]
        self.children = self.children[:center + 1]
        return sibling, median

    def insert(self, index, item, ancestors):
        self.contents.insert(index, item)
        if len(self.contents) > self.tree.order:
            self.shrink(ancestors)

    def remove(self, index, ancestors):
        minimum = self.tree.order // 2

        if self.children:
            # try promoting from the right subtree first,
            # but only if it won't have to resize
            additional_ancestors = [(self, index + 1)]
            descendent = self.children[index + 1]
            while descendent.children:
                additional_ancestors.append((descendent, 0))
                descendent = descendent.children[0]
            if len(descendent.contents) > minimum:
                ancestors.extend(additional_ancestors)
                self.contents[index] = descendent.contents[0]
                descendent.remove(0, ancestors)
                return

            # fall back to the left child
            additional_ancestors = [(self, index)]
            descendent = self.children[index]
            while descendent.children:
                additional_ancestors.append(
                    (descendent, len(descendent.children) - 1))
                descendent = descendent.children[-1]
            ancestors.extend(additional_ancestors)
            self.contents[index] = descendent.contents[-1]
            descendent.remove(len(descendent.children) - 1, ancestors)
        else:
            self.contents.pop(index)
            if len(self.contents) < minimum and ancestors:
                self.grow(ancestors)


class BTree(object):
    BRANCH = LEAF = _BNode

    def __init__(self, order):
        self.order = order
        self._root = self._bottom = self.LEAF(self)

    def _path_to(self, item):
        current = self._root
        ancestry = []

        while getattr(current, "children", None):
            index = bisect.bisect_left(current.contents, item)
            ancestry.append((current, index))
            if index < len(current.contents) \
                    and current.contents[index] == item:
                return ancestry
            current = current.children[index]

        index = bisect.bisect_left(current.contents, item)
        ancestry.append((current, index))
        present = index < len(current.contents)
        present = present and current.contents[index] == item

        return ancestry

    def _present(self, item, ancestors):
        last, index = ancestors[-1]
        return index < len(last.contents) and last.contents[index] == item

    def insert(self, item):
        current = self._root
        ancestors = self._path_to(item)
        node, index = ancestors[-1]
        while getattr(node, "children", None):
            node = node.children[index]
            index = bisect.bisect_left(node.contents, item)
            ancestors.append((node, index))
        node, index = ancestors.pop()
        node.insert(index, item, ancestors)

    def remove(self, item):
        current = self._root
        ancestors = self._path_to(item)

        if self._present(item, ancestors):
            node, index = ancestors.pop()
            node.remove(index, ancestors)
        else:
            raise ValueError("%r not in %s" % (item, self.__class__.__name__))

    def __contains__(self, item):
        return self._present(item, self._path_to(item))

    def __iter__(self):
        def _recurse(node):
            if node.children:
                for child, item in zip(node.children, node.contents):
                    for child_item in _recurse(child):
                        yield child_item
                    yield item
                for child_item in _recurse(node.children[-1]):
                    yield child_item
            else:
                for item in node.contents:
                    yield item

        for item in _recurse(self._root):
            yield item

    def __repr__(self):
        def recurse(node, accum, depth):
            accum.append(("  " * depth) + repr(node))
            for node in getattr(node, "children", []):
                recurse(node, accum, depth + 1)

        accum = []
        recurse(self._root, accum, 0)
        return "\n".join(accum)

    @classmethod
    def bulkload(cls, items, order):
        tree = BTree(order)
        tree.order = order

        leaves = tree._build_bulkloaded_leaves(items)
        tree._build_bulkloaded_branches(leaves)

        return tree

    def _build_bulkloaded_leaves(self, items):
        minimum = self.order // 2
        leaves, seps = [[]], []

        for item in items:
            if len(leaves[-1]) < self.order:
                leaves[-1].append(item)
            else:
                seps.append(item)
                leaves.append([])

        if len(leaves[-1]) < minimum and seps:
            last_two = leaves[-2] + [seps.pop()] + leaves[-1]
            leaves[-2] = last_two[:minimum]
            leaves[-1] = last_two[minimum + 1:]
            seps.append(last_two[minimum])

        return [[self.LEAF(self, contents=node) for node in leaves], seps]

    def _build_bulkloaded_branches(self, param):
        minimum = self.order // 2
        leaves = param[0]
        seps = param[1]
        levels = [leaves]

        while len(seps) > self.order + 1:
            items, nodes, seps = seps, [[]], []

            for item in items:
                if len(nodes[-1]) < self.order:
                    nodes[-1].append(item)
                else:
                    seps.append(item)
                    nodes.append([])

            if len(nodes[-1]) < minimum and seps:
                last_two = nodes[-2] + [seps.pop()] + nodes[-1]
                nodes[-2] = last_two[:minimum]
                nodes[-1] = last_two[minimum + 1:]
                seps.append(last_two[minimum])

            offset = 0
            for i, node in enumerate(nodes):
                children = levels[-1][offset:offset + len(node) + 1]
                nodes[i] = self.BRANCH(self, contents=node, children=children)
                offset += len(node) + 1

            levels.append(nodes)

        self._root = self.BRANCH(self, contents=seps, children=levels[-1])


# this class represents a node within a tree within a Fibonacci heap;
# i.e., the actual elements of the heap
# it contains fields for the necessary key, value, and children data,
# but also has fields to describe its relationship with its sibling
# nodes as well as its markedness status
# it contains methods for adding to and cutting children from this node
class TreeNode():
    def __init__(self, key, url):
        #the key contains the distance value
        self.key = key
        #this contains the url string of itself
        self.self_url = url
        # this contains the list of neighbors (e.g., list of tnodes
        # corresponding to urls that I link to)
        # list will be list of refs to these tnodes
        self.neighbors = []
        # this contains a ref to the tnode which leads back to the
        # starting url in the most shortest route
        self.dij_prev = None
        # this means that it was processed through Dijkstra's
        self.finished = False
        # the following are fib heap requirements
        self.prev = None
        self.next = None
        self.children = []
        self.marked = False
        # added pointer to parent, if any
        self.parent = None
        # pointer to enclosing CircNode, if any
        self.cnode = None

    # adds a child to this parent node, updating its linked-list of children
    # O(1)
    def add_child(self, new_child):
        if len(self.children) > 0:
            # new_child's 'prev' should point to end of children list
            new_child.prev = self.children[-1]
            # new_child's 'next' should be the same as last child's
            # 'next' (e.g., None)
            new_child.next = self.children[-1].next
            # last child's next now points to the new child
            self.children[-1].next = new_child
        # new child points to parent
        new_child.parent = self
        #actually add the child to the children list
        self.children.append(new_child)

    # cuts a child, updating linked-list of children and returning cut node
    # also sets this node's marked status to TRUE
    # O(n) where n = len(self.children)
    def cut_child(self, cut_index):
        # in case of out-of-bound values for cut_index
        if cut_index >= len(self.children) or cut_index < 0:
            return None

        if cut_index + 1 < len(self.children) and cut_index > 0:
            # connect (child after the one to be cut) to
            # (child before the one to be cut)
            self.children[cut_index + 1].prev = self.children[cut_index - 1]
            # connect (child before the one to be cut) to
            # (child after the one to be cut)
            self.children[cut_index - 1].next = self.children[cut_index + 1]
        #case of cutting the first element
        elif cut_index + 1 <= len(self.children) - 1 and cut_index - 1 < 0:
            self.children[1].prev = None
        # case of cutting the last element
        elif cut_index + 1 > len(self.children) - 1 and cut_index - 1 >= 0:
            self.children[cut_index - 1].next = None

        # remove that child from the list
        # (now that links are re-done to cut this out)
        new_root = self.children.pop(cut_index)
        # mark the parent
        #self.marked = True
        new_root.prev = new_root
        new_root.next = new_root
        new_root.parent = None
        new_root.marked = False
        # the caller will have to take care of inserting the new root
        # into the ring of roots
        return new_root

    def print_treenode_and_children(self, tnode, s):
        for child in tnode.children:
            if len(child.children) > 0:
                child.print_treenode_and_children(child, '\t' + s)

    def treenode_and_children_to_list(self, tnode):
        a_list = []
        for child in tnode.children:
            a_list.extend(child.self_url)
            if len(child.children) > 0:
                a_list.extend(child.self_url)
        return a_list

    def find(self, key):
        #check your own key
        if self.key == key:
            return self
        #check all your children's recursively
        if len(self.children) > 0:
            for child in self.children:
                temp_answer = child.find(key)
                if temp_answer is not None:
                    return temp_answer
        else:
            return None

    def find_on_self_url(self, url):
        #check your own url
        if self.self_url == url:
            return self
        #check all your children's recursively
        if len(self.children) > 0:
            for child in self.children:
                temp_answer = child.find_on_self_url(url)
                if temp_answer is not None:
                    return temp_answer
            return None


# this class represents one of the trees the Fibonacci heap is a collection of
# it holds a reference to the root node of the tree and the degree of the
#   tree (number of children its root has)
# it has methods for adding to and cutting nodes from the tree, as well as
#   for merging this tree with another tree
class Tree():
    def __init__(self, tnode):
        self.root = tnode

    def __getattr__(self, attr):
        if attr == "degree":
            return len(getattr(self.root, "children"))

    def add(self, tnode):
        # YJP: changed this around to be consistent with other functions
        # if the node to be added is less than root, root becomes
        # child of the node to be added
        self.root.add_child(tnode)

    def cut(self, tnode):
        #index returns the index pos of first occurrence of tnode in list
        new_root = self.root.cut_child(self.root.children.index(tnode))
        return Tree(new_root)

    def merge_with(self, tree):
        if self.root.key < tree.root.key:
            self.add(tree.root)
            return self
        else:
            tree.add(self.root)
            return tree

    def print_tree(self):
        print('Tree root:' + repr(self.root.key) + 'Tree root self_url:' + repr(
            self.root.self_url) + 'Tree root number of neighbors: ' + repr(len(self.root.neighbors)))
        print("Tree degree:" + repr(self.degree))
        self.root.print_treenode_and_children(self.root, '')

    def tree_to_list(self):
        a_list = [self.root.self_url]
        a_list.extend(self.root.treenode_and_children_to_list(
            self.root))
        return a_list


# this class represents a node of the linked list at the core of the Fibonacci
# heap; it is a wrapper for the tree that is the actual list element
# it contains the tree as well as fields to maintain the doubly linked list
# it contains methods to look at the key at the top of its tree and to merge
# itself with another CircNode
class CircNode():
    def __init__(self, tree):
        tree.root.marked = False
        tree.root.parent = None
        tree.root.prev = tree.root.next = tree.root
        tree.root.cnode = self
        self.tree = tree
        self.prev = self.next = self
        self.checked_for_consolidation = False

    def key(self):
        return self.tree.root.key

    def merge(self, other_node):
        lower_key_tree = self.tree.merge_with(other_node.tree)


class FibHeap():
    def __init__(self):
        self.min = None
        # size here refers to number of nodes in the core doubly-linked
        # list/ring, NOT total number of nodes in the heap
        self.size = 0
        # the below refers to total number of nodes in the fibheap
        # (not just in the ring)
        self.total_size = 0

    # returns whether or not this heap is empty
    def is_empty(self):
        return self.min is None

    # inserts the given TreeNode into the heap at the circnode level
    # ("adds a new tree")
    def insert(self, tnode):
        tnode.parent = None
        cnode = CircNode(Tree(tnode))
        if self.is_empty():
            self.min = cnode
        else:
            # always insert cnode before the current min
            cnode.prev = self.min.prev
            cnode.next = self.min
            self.min.prev.next = cnode
            self.min.prev = cnode
            if cnode.tree.root.key < self.min.tree.root.key:
                self.min = cnode
        self.size += 1
        self.total_size += 1
        print("after an insert*************")
        self.print_heap()
        return cnode

    # returns the minimum element of the heap (as a TreeNode) without
    # removing it
    def get_min(self):
        return self.min.tree.root

    # returns the minimum element of the heap (as a TreeNode) and removes
    # it from the heap
    def pop(self):
        print("\npop happened ***************")
        if self.is_empty():
            return None
        else:
            returnval = self.min.tree.root
            # there is only one cnode left and it has no children
            if (self.min.next is self.min) and self.min.tree.degree == 0:
                self.min = None
                self.total_size -= 1
                self.size -= 1
                return returnval
            # min is not the only cnode left but min has no children
            elif (self.min.next is not self.min) and self.min.tree.degree == 0:
                self.min.prev.next = self.min.next
                self.min.next.prev = self.min.prev
                self.min = self.min.next
                self.restructure()
                self.total_size -= 1
                self.size -= 1
                return returnval
            # min is the only cnode left and it has children
            elif self.min.next is self.min:
                self.min.tree.root.children[0].parent = None
                new_head = CircNode(Tree(self.min.tree.root.children[0]))
                new_tail = new_head
                if self.min.tree.degree > 1:
                    curr_child = new_head
                    for child in self.min.tree.root.children[1:]:
                        child.parent = None
                        curr_child.next = CircNode(Tree(child))
                        curr_child.next.prev = curr_child
                        curr_child = curr_child.next
                        if child == self.min.tree.root.children[-1]:
                            new_tail = curr_child
                new_head.prev = new_tail
                new_tail.next = new_head
                self.size += (len(self.min.tree.root.children) - 1)
                self.total_size -= 1
                self.min = new_head
                self.restructure()
                return returnval
            # min is not the only cnode left and it has children
            else:
                self.min.tree.root.children[0].parent = None
                new_head = CircNode(Tree(self.min.tree.root.children[0]))
                new_tail = new_head
                if self.min.tree.degree > 1:
                    curr_child = new_head
                    for child in self.min.tree.root.children[1:]:
                        child.parent = None
                        curr_child.next = CircNode(Tree(child))
                        curr_child.next.prev = curr_child
                        curr_child = curr_child.next
                        if child == self.min.tree.root.children[-1]:
                            new_tail = curr_child
                self.min.prev.next = new_head
                new_head.prev = self.min.prev
                self.min.next.prev = new_tail
                new_tail.next = self.min.next
                self.size += (len(self.min.tree.root.children) - 1)
                self.total_size -= 1
                self.min = new_head
                self.restructure()
                return returnval

    # restructures the heap's core double-linked-list after the removal
    # of one of the heap's elements (circnode ring exists but
    # consolidation hasn't happened yet
    # also, haven't set a new, correct self.min yet
    def restructure(self):
        degrees = [None]
        currCNode = self.min
        while True:
            #the largest degree that we are tracking
            max_degree = len(degrees) - 1
            #to get the right min by the end
            temp_min_key = self.min.key()
            if currCNode.key() <= temp_min_key:
                self.min = currCNode
                temp_min_key = self.min.key()
            # if we run across a cnode with a degree larger than we are tracking
            if currCNode.tree.degree > max_degree:
                print("THIS IS THE PROBLEM AREA!! (A)**********")
                for i in range(max_degree, currCNode.tree.degree):
                    degrees.append(None)
                degrees[currCNode.tree.degree] = currCNode
                currCNode = currCNode.next
                continue
            # if we have come all the way back to the same cnode, and the next
            # cnode has been checked to have no duplicates either, we've run
            # the whole ring
            if degrees[currCNode.tree.degree] is currCNode:
                print("THIS IS THE PROBLEM AREA!! (B)**********")
                currCNode.checked_for_consolidation = True
                if currCNode.next.checked_for_consolidation:
                    break
                else:
                    currCNode = currCNode.next
                    continue
            if degrees[currCNode.tree.degree] is None:
                print("THIS IS THE PROBLEM AREA!! (C)**********")
                degrees[currCNode.tree.degree] = currCNode
                currCNode = currCNode.next
            else:
                # this is the cnode prev identified as one having same degree
                # as our current cnode
                mergeNode = degrees[currCNode.tree.degree]
                degrees[currCNode.tree.degree] = None
                if mergeNode.key() < currCNode.key():
                    print("THIS IS THE PROBLEM AREA!! (D)**********")
                    print("mergeNode is " + repr(mergeNode.tree.root.self_url) + "with key " + repr(
                        mergeNode.tree.root.key) + "and with degree " + repr(mergeNode.tree.degree))
                    print("currCNode is " + repr(currCNode.tree.root.self_url) + "with key " + repr(
                        currCNode.tree.root.key) + "and with degree " + repr(currCNode.tree.degree))
                    mergeNode.prev.next = mergeNode.next
                    mergeNode.next.prev = mergeNode.prev
                    mergeNode.next = currCNode.next
                    mergeNode.prev = currCNode.prev
                    currCNode.prev.next = mergeNode
                    currCNode.next.prev = mergeNode
                    mergeNode.tree.root.add_child(currCNode.tree.root)
                    if currCNode is self.min:
                        self.min = mergeNode
                    currCNode = mergeNode
                else:
                    print("THIS IS THE PROBLEM AREA!! (E)**********")
                    self.remove_node(mergeNode)
                    currCNode.tree.root.add_child(mergeNode.tree.root)
                    if mergeNode is self.min:
                        self.min = currCNode
                currCNode.checked_for_consolidation = False
                self.size -= 1
            print("\nafter one iteration of restructure*******************")
            self.print_heap()

    def remove_node(self, cnode):
        cnode.prev.next = cnode.next
        cnode.next.prev = cnode.prev
        cnode.prev = cnode.next = cnode
        return cnode

    # decreases the key of the given TreeNode to the specified value,
    # cutting children off into new trees if the min-heap invariant becomes
    # violated in the new configuration
    def decr_key(self, tnode, new_key):
        print("Decr_key happened! ********************")
        #print "decr-ing tnode %g to %g" % (tnode.key,new_key)
        if new_key >= tnode.key:
            print("New key must be less than old key")
        else:
            tnode.key = new_key
            if tnode.parent is not None:
                if tnode.key < tnode.parent.key:
                    #fix_heap uses insert, which should update the min
                    self.fix_heap_recursive(tnode)
            elif tnode.key < self.min.tree.root.key:
                self.min = tnode.cnode

    def fix_heap_recursive(self, tnode):
        if tnode.parent is not None:
            theParent = tnode.parent
            parent_marked = theParent.marked
            new_root = theParent.cut_child(theParent.children.index(tnode))
            self.insert(new_root)
            if parent_marked:
                self.fix_heap_recursive(theParent)
            else:
                theParent.marked = True

    # removes the given TreeNode from the heap (does not return the node)
    def delete(self, tnode):
        self.decr_key(tnode, float("-inf"))
        self.pop()

    # merges this heap with another Fibonacci heap
    def merge(self, other_heap):
        other_heap.min.prev.next = self.min.next
        self.min.next.prev = other_heap.min.prev
        self.min.next = other_heap.min
        other_heap.min.prev = self.min
        if other_heap.min.tree.root.key < self.min.tree.root.key:
            self.min = other_heap.min
        self.size += other_heap.size
        self.total_size += other_heap.total_size

    # returns the TreeNode with the given key, or None if key not in heap
    def find(self, key):
        start_circnode = self.min
        curr_circnode = self.min
        answer_tnode = curr_circnode.tree.root.find(key)
        if answer_tnode is not None:
            return answer_tnode
        while True:
            if curr_circnode.next == start_circnode:
                return None
            curr_circnode = curr_circnode.next
            answer_tnode = curr_circnode.tree.root.find(key)
            if answer_tnode is not None:
                return answer_tnode

    def find_on_self_url(self, url):
        #if heap is entirely empty, then return None
        if self.is_empty():
            return None
        start_circnode = self.min
        curr_circnode = self.min
        answer_tnode = curr_circnode.tree.root.find_on_self_url(url)
        if answer_tnode is not None:
            return answer_tnode
        while True:
            if curr_circnode.next == start_circnode:
                return None
            curr_circnode = curr_circnode.next
            answer_tnode = curr_circnode.tree.root.find_on_self_url(url)
            if answer_tnode is not None:
                return answer_tnode

    # yjp: prints all the nodes in the heap, and use for testing
    def print_heap(self):
        print("\nThis is a heap of total size" + repr(self.total_size))
        print("This is key of min cnode" + repr(self.min.key()))
        curr_circnode = self.min
        print("\nthis is a circnode:")
        curr_circnode.tree.print_tree()
        while curr_circnode.next is not self.min:
            curr_circnode = curr_circnode.next
            print("\nthis is a circnode:")
            curr_circnode.tree.print_tree()

    #yjp: prints a numbered list of the urls of all the tnodes in the fibheap
    def heap_to_list(self):
        curr_circnode = self.min
        a_list = curr_circnode.tree.tree_to_list()
        while curr_circnode.next is not self.min:
            curr_circnode = curr_circnode.next
            a_list.extend(curr_circnode.tree.tree_to_list())
        return a_list

    # cjl: prints only the keys of the nodes in the core doubly-linked list.
    #      this is used to check correct circularity of list.
    def print_CDDL(self):
        print("\nHeap CDDL:")
        curr_circnode = self.min
        print("Circnode " + repr(curr_circnode.tree.root.key))
        while curr_circnode.next is not self.min:
            curr_circnode = curr_circnode.next
            print("Circnode " + repr(curr_circnode.tree.root.key))


__author__ = "Evan Jones <evanj@mit.edu>"

import bisect
import math


def log2(n):
    return math.log2(n)


class VEBQueueSmall():
    def __init__(self):
        """Creates a "VEB" queue containing only 2 items."""
        self.values = [False, False]

    def insert(self, x):
        assert 0 <= x < 2
        self.values[x] = True

    def delete(self, x):
        assert 0 <= x < 2
        self.values[x] = False

    def find(self, x):
        assert 0 <= x < 2
        return self.values[x]

    def max(self):
        for i in range(1, -1, -1):
            if self.values[i]:
                return i
        return None

    def min(self):
        for i in range(2):
            if self.values[i]:
                return i
        return None

    def predecessor(self, x):
        assert 0 <= x < 2

        if x == 0:
            return None
        assert x == 1
        if self.values[0]:
            return 0


def NewVEBQueue(n):
    if n == 2:
        return VEBQueueSmall()
    else:
        return VEBQueueBase(n)


class VEBQueueBase():
    def __init__(self, n):
        """Create a queue containing (0, n-1). n must be = 2^(2^x)."""

        try:
            power = log2(n)
            powpow = log2(n)
        except OverflowError:
            raise ValueError("n must be = 2^(2^x) for some x")

        self.sqrtShift = power / 2
        sqrtN = 1 << int(self.sqrtShift)
        self.sqrtMask = sqrtN - 1
        self.n = n

        self.high = NewVEBQueue(sqrtN)
        self.low = [None] * sqrtN
        self.minValue = None
        self.maxValue = None

    def split(self, x):
        """Returns the high and low portions of x."""

        xHigh = x >> int(self.sqrtShift)
        xLow = x & self.sqrtMask
        return xHigh, xLow

    def insert(self, x):
        assert 0 <= x < self.n

        if self.minValue is None:
            # Insert in empty queue: O(1)
            assert self.maxValue is None
            self.minValue = x
            self.maxValue = x
            return
        if x == self.minValue:
            # Inserting the minimum again does nothing
            return

        if x < self.minValue:
            # Inserting less than min: actually insert min
            oldMin = self.minValue
            self.minValue = x
            x = oldMin
        assert x > self.minValue

        if x > self.maxValue:
            self.maxValue = x

        xHigh, xLow = self.split(x)

        if self.low[xHigh] is None:
            # Empty sub-queue: Create it
            self.low[xHigh] = NewVEBQueue(1 << int(self.sqrtShift))
            self.high.insert(xHigh)
        self.low[xHigh].insert(xLow)

    def delete(self, x):
        assert 0 <= x < self.n

        if self.minValue is None:
            # Delete in empty queue: do nothing
            return
        if x < self.minValue:
            # x does not exist in the queue
            return
        assert x >= self.minValue

        if x == self.minValue:
            # Move the successor to the minimum value and delete that instead
            index = self.high.min()
            if index is None:
                # No successor: we are done
                assert self.maxValue == self.minValue
                self.minValue = None
                self.maxValue = None
                return

            self.minValue = (index << self.sqrtShift) | self.low[index].min()
            x = self.minValue

        xHigh, xLow = self.split(x)

        if self.low[xHigh] is None:
            # Nothing to delete
            return

        # The queue for x must exist. Delete it recursively
        self.low[xHigh].delete(xLow)

        if self.low[xHigh].min() is None:
            # Sub queue is now empty: delete it from the high queue
            self.low[xHigh] = None
            self.high.delete(xHigh)

        if x == self.maxValue:
            # If we deleted the maximum, update it in O(1) time
            maxHigh = self.high.max()
            if maxHigh is None:
                # 1 element in this queue
                assert self.minValue is not None
                self.maxValue = self.minValue
            else:
                self.maxValue = (maxHigh << self.sqrtShift) | self.low[maxHigh].max()

    def max(self):
        return self.maxValue

    def min(self):
        return self.minValue

    def find(self, x):
        assert 0 <= x < self.n

        if self.minValue is None:
            return False
        if x == self.minValue:
            return True
        xHigh, xLow = self.split(x)
        if self.low[xHigh] is None:
            return False
        return self.low[xHigh].find(xLow)

    def predecessor(self, x):
        assert 0 <= x < self.n

        if self.minValue is None or x <= self.minValue:
            # Empty queue or nothing smaller
            return None

        xHigh, xLow = self.split(x)
        if self.low[xHigh] is None or xLow <= self.low[xHigh].min():
            # We need to look before this block: recurse on self.high O(sqrt n)
            index = self.high.predecessor(xHigh)
            if index is None:
                # No predecessors in self.high: Return the min
                return self.minValue

            # Combine the index with the max from the lower block
            return (index << self.sqrtShift) | self.low[index].max()
        else:
            assert xLow > self.low[xHigh].min()
            # We need to look in this block: recurse on self.low O(sqrt n)
            lowerPredecessor = self.low[xHigh].predecessor(xLow)
            assert lowerPredecessor is not None
            return (xHigh << self.sqrtShift) | lowerPredecessor


if __name__ == '__main__':

    bt = BTree(2)
    for i in range(97, 112):
        bt.insert(i)

    print(bt)

    fh = FibHeap()

    for i in range(0, 20):
        new_node = TreeNode(i, "yahoo")
        fh.insert(new_node)

    fh.print_heap()

    #Need to establish n must be n=2^(2^x)
    veb = NewVEBQueue(256)
    for i in range(0, 256):
        for j in range(0, 10):
            veb.insert(i)

    print("Done")