class Node:
    def __init__(self, val):
        self.val = val
        self.nxt = None


class LinkedList:
    def __init__(self):
        self.head = None

    def insertAtFront(self, val):
        tmp = self.head
        self.head = Node(val)
        self.head.nxt = tmp

    def insertAtEnd(self, val):
        if self.head:
            tmp = self.head
            while True:
                if tmp.nxt is None:
                    tmp.nxt = Node(val)
                    break
                else:
                    tmp = tmp.nxt
        else:
            self.head = Node(val)

    def insertAfter(self, val_1, val_2):  # Assuming all values are distinct. If not, we need to use "keys" for nodes.
        """inserts a node with value val_1 after the node with value val_2"""
        if self.head is None:
            print "There is no node with value " + str(val_2)
            return
        else:
            cur = self.head
            while True:
                if cur.val == val_2:
                    tmp = Node(val_1)
                    tmp.nxt = cur.nxt
                    cur.nxt = tmp
                    break
                else:
                    if cur.nxt is not None:
                        cur = cur.nxt
                    else:
                        print "There is no node with value " + str(val_2)
                        return

    def insertBehind(self, val_1, val_2):  # Assuming all values are distinct. If not, we need to use 'keys' for nodes.
        """inserts a node with value val_1 behind the node with value val_2"""
        if self.head is None:
            print "There is no node with value " + str(val_2)
        else:
            if val_2 == self.head:
                self.insertAtFront(val_1)
            else:
                cur = self.head
                while True:
                    if cur.nxt.val == val_2:
                        tmp = Node(val_1)
                        tmp.nxt = cur.nxt
                        cur.nxt = tmp
                        break
                    else:
                        if cur.nxt:
                            cur = cur.nxt
                        else:
                            print "There is no node with value " + str(val_2)
                            break

    def reverse(self):
        cur = self.head
        prev = None
        next = cur.nxt
        while True:
            cur.nxt = prev
            if next is None:
                break
            prev = cur
            cur = next
            next = next.nxt
        self.head = cur

    def __str__(self):
        if self.head is None:
            return "The linked list is empty"
        else:
            cur = self.head
            output = []
            while cur is not None:
                output.append(cur.val)
                cur = cur.nxt
            return ''.join(str(i) + ' -> ' for i in output)[:-4]  # '-4' is for excluding the last arrow and spaces

class Stack(object):
    def __init__(self):
        self.items = []

    def is_empty(self):
        return self.size() == 0

    def push(self, m):
        self.items.append(m)

    def pop(self):
        if self.is_empty():
            print "The list is empty"
        else:
            self.items.pop()

    def peek(self):
        if self.is_empty():
            print "The List is Empty"
        else:
            return self.items[-1]

    def size(self):
        return len(self.items)

    def __str__(self):
        return str(self.items)

class Queue(object):
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self, item):
        self.items.insert(0, item)

    def dequeue(self):
        return self.items.pop()

    def peek(self):
        return self.items[-1]

class Node(object):
    def __init__(self, val):
        self.value = val
        self.left = None
        self.right = None


class BinaryTree(object):
    def __init__(self):
        self.root = None

    def addLeft(self, val):
        """Adds a node with value 'val' to immediate left of the root"""
        if self.root is None:
            self.root = Node(val)
        elif self.root.left is None:
            self.root.left = Node(val)
        else:
            tmp = Node(val)
            tmp.left = self.root.left
            self.root.left = tmp

    def addRight(self, val):
        """Adds a node with value 'val' to immediate right of the root"""
        tmp = Node(val)
        if self.root is None:
            self.root = tmp
        elif self.root.right is None:
            self.root.right = Node(val)
        else:
            tmp.right = self.root.right
            self.root.right = tmp

    def addAtRootL(self, val):
        """creates a node with value 'val' and attaches the tree to the left of it"""
        tmp = Node(val)
        if self.root is None:
            self.root = tmp
        else:
            tmp.left = self.root
            self.root = tmp

    def addAtRootR(self, val):
        """Creates a node with value 'val' and attaches the tree to the right of it"""
        tmp = Node(val)
        if self.root is None:
            self.root = tmp
        else:
            tmp.right = self.root
            self.root = tmp

    def inorder(self):
        """One of Depth-First Traversal Methods"""
        if self.root:
            self._inOrder(self.root)
        else:
            print 'The tree is empty'

    def _inOrder(self, node):
        if node:
            self._inOrder(node.left)
            print node.value
            self._inOrder(node.right)

    def levelOrder(self):
        """Breadth-First Traversal"""
        from Queue import Queue
        q = Queue()
        q.enqueue(self.root)
        while not q.isEmpty():
            node = q.dequeue()
            print node.value
            if node.left:
                q.enqueue(node.left)
            if node.right:
                q.enqueue(node.right)

    def levelOrder2(self):
        """Another Breadth-First Traversal without using a Queue"""
        print self.root.value
        l1 = [self.root]  # contains nodes at each level
        while True:
            l2 = []
            output = ''
            for i in l1:
                if i.left:
                    output += str(i.left.value) + ' '
                    l2.append(i.left)
                if i.right:
                    output += str(i.right.value) + ' '
                    l2.append(i.right)
            print output
            if not l2:
                break
            l1 = l2[:]

class Node(object):
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None


class BST(object):  # Binary Search Tree
    def __init__(self):
        self.root = None

    def add(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            self._add(value, self.root)

    def _add(self, value, node):
        if value < node.value:
            if node.left:    # i.e. if node.left is not 'None'
                self._add(value, node.left)
            else:
                node.left = Node(value)
        else:
            if node.right:
                self._add(value, node.right)
            else:
                node.right = Node(value)

    def create_bst(self, alist):
        self.root = BST._create_bst(alist, 0, len(alist) - 1)

    @staticmethod
    def _create_bst(alist, start, end):
        if end < start:
            return None
        mid = (start + end) / 2
        root = Node(alist[mid])
        root.right = BST._create_bst(alist, mid + 1, end)
        root.left = BST._create_bst(alist, start, mid - 1)
        return root


b = BST()
b.create_bst([1, 2, 3])

from heapq import heappop, heappush

class MinHeap(object):
    def __init__(self):
        self.items = []

    def insert(self, val):
        heappush(self.items, val)

    def extract_min(self):
        heappop(self.items)

    def get_min(self):
        return self.items[0]

    def __str__(self):
        return str(self.items)

class MinHeap(object):
    def __init__(self):
        self.items = []

    def insert(self, val):
        self.items.append(val)
        self.heapify_up()

    def extract_min(self):
        self.items[0] = self.items[-1]
        self.items.pop()
        self.heapify_down()

    def get_min(self):
        return self.items[0]

    def __str__(self):
        return str(self.items)

    # The rest is for defining heapify

    @staticmethod
    def get_parent(index):
        if index == 0:
            print "Root has no parent"
            return None
        return (index - 1) / 2

    def has_left_child(self, index):
        return 2 * index + 1 < len(self.items)

    def has_right_child(self, index):
        return 2 * index + 2 < len(self.items)

    def swap(self, i, j):
        self.items[i], self.items[j] = self.items[j], self.items[i]

    def heapify_up(self):
        cur_index = len(self.items) - 1
        while cur_index > 0:
            par = self.get_parent(cur_index)
            if self.items[par] > self.items[cur_index]:
                self.swap(par, cur_index)
            cur_index -= 1

    def heapify_down(self):
        cur_index = 0
        while 2 * cur_index + 1 < len(self.items):
            left_child = 2 * cur_index + 1
            if self.has_right_child(cur_index):
                right_child = 2 * cur_index + 2
                child = self.items.index(min(self.items[left_child], self.items[right_child]))
            else:
                child = left_child
            if self.items[child] < self.items[cur_index]:
                self.swap(child, cur_index)
            cur_index += 1

# Since heapq methods work for MinHeap, here for MaxHeap we use them for negated values.
# At the end we negate again to get the desired output.

# If values are not numbers (int, float) we need to redefine __lt__ (see https://stackoverflow.com/a/40455775/2445273).

from heapq import heappop, heappush

class MaxHeap(object):
    def __init__(self):
        self.items = []

    def insert(self, val):
        heappush(self.items, -val)

    def extract_min(self):
        heappop(self.items)

    def get_min(self):
        return -self.items[0]

    def __str__(self):
        return str([-x for x in self.items])

from Queue import Queue

class Node(object):
    def __init__(self, key, neighbours):
        self.key = key
        self.neighbors = neighbours
        self.visited = False
        self.parent = None  # Is needed for finding the shortest path using BFS

class Graph(object):
    """nodes and edges are given as an adjacency list.
        Adjacency list itself is given as a tuple of node key and a list of its neighbors"""
    def __init__(self, nodes):
        self.nodes = [Node(item[0], item[1]) for item in nodes]
        self.flag = False   # auxiliary variable used in _dfs2 method

    def __str__(self):
        for item in self.nodes:
            print str(item.key) + ' : ' + ''.join(str(i) + ', ' for i in item.neighbors)[:-2]
        return ''

    def get_node(self, key):
        for node in self.nodes:
            if node.key == key:
                return node
        print 'not found!'
        return None

    def dfs(self, key):
        """Explores the graph rooted at 'key' using Depth-First Search"""
        node = self.get_node(key)
        if not node.visited:
            print node.key
            node.visited = True
            for i in node.neighbors:
                self.dfs(i)
        # Reverting the visited status of all nodes not 'not visited'
        for node in self.nodes:
            node.visited = False

    def dfs2(self, start, end):
        """Finds a path between start and end or the reverse direction if one exists
            using Depth-First Search"""

        def _dfs2(_start, _end, _tmp_path):
            global path
            if self.flag:   # if the destination node has been reached, stop nested recursions
                return
            s = self.get_node(_start)
            if not s.visited:
                s.visited = True
                tmp_path_copy = _tmp_path[:]
                tmp_path_copy.append(s.key)
                for node in s.neighbors:
                    if node == _end:    # if the destination node has been reached
                        self.flag = True
                        tmp_path_copy.append(node.key)
                        path = tmp_path_copy
                        return
                    _dfs2(node, end, tmp_path_copy)

            # Reverting back the visited status of all nodes to 'not visited'
            for node in self.nodes:
                node.visited = False

            if self.flag:
                return path

        tmp_path = []
        a = _dfs2(start, end, tmp_path)
        b = _dfs2(end, start, tmp_path)
        if a:
            print 'There is a path between {} and {}: {}'.format(start, end, a)
        if b:
            print 'There is a path between {} and {}: {}'.format(end, start, b)
        if not a and not b:
            print 'There is no path between {} and {}'.format(start, end)

    def bfs(self, key):
        """Explores the graph rooted at 'key' using Breadth-First Search"""
        node = self.get_node(key)
        q = Queue()
        q.enqueue(node)
        node.visited = True
        while not q.isEmpty():
            n = q.dequeue()
            print n.key
            for node in n.neighbors:
                if not node.visited:
                    q.enqueue(node)
                    node.visited = True
        # Reverting the visited status of all nodes not 'not visited'
        for node in self.nodes:
            node.visited = False

    def bfs2(self, start, end):
        """Finds a path between start and end or the reverse direction if one exists
            using Breadth-First Search"""

        def _bfs2(_start, _end):
            q = Queue()
            s = self.get_node(_start)
            q.enqueue(s)
            while not q.isEmpty():
                node = q.dequeue()
                if node.key == _end:
                    _path = []
                    while True:
                        _path.append(node.key)
                        if not node.parent:  # reached the root node
                            _path.reverse()
                            break
                        node = node.parent
                    return _path
                for i in node.neighbors:
                    n = self.get_node(i)
                    if not n.visited:
                        n.visited = True
                        n.parent = node
                        q.enqueue(n)

            # Reverting back the visited status of all nodes to 'not visited'
            for node in self.nodes:
                node.visited = False

            return False

        a = _bfs2(start, end)
        b = _bfs2(end, start)
        if a:
            print 'There is a path between {} and {}: {}'.format(start, end, a)
        if b:
            print 'There is a path between {} and {}: {}'.format(end, start, b)
        if not a and not b:
            print 'There is no path between {} and {}'.format(start, end)


g = Graph([('a', ['b', 'c']), ('b', ['c', 'd']), ('c', ['e', 'f']), ('d', []), ('e', []), ('f', []), ('g', [])])
print g
g.bfs2('a', 'e')

# runtime: O(nlog(n)), space: O(n)

def mergesort(alist):
    if len(alist) == 1:
        return alist
    mid = len(alist) / 2
    return merge(mergesort(alist[:mid]), mergesort(alist[mid:]))

def merge(list1, list2):
    output = []
    n, m = 0, 0
    while True:
        if list1[m] < list2[n]:
            output.append(list1[m])
            m += 1
        else:
            output.append(list2[n])
            n += 1
        if not list1[m:]:
            for i in list2[n:]:
                output.append(i)
            break
        elif not list2[n:]:
            for i in list1[m:]:
                output.append(i)
            break
    return output

# Runtime: avg O(nlog(n)) worst O(n^2), space: no space other than the list itself

def quicksort(alist, left, right):
    index = partition(alist, left, right)
    if index - 1 > left:
        quicksort(alist, left, index - 1)
    if index < right:
        quicksort(alist, index, right)


def partition(alist, left, right):
    pivot = alist[(left + right) / 2]
    while left <= right:
        while alist[left] < pivot:
            left += 1
        while alist[right] > pivot:
            right -= 1
        if left <= right:
            alist[left], alist[right] = alist[right], alist[left]
            left += 1
            right -= 1
    return left