<file_sep>class Node(object):

    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None


class BST(object):

    def __init__(self):
        self.root = None

    def insert(self,data):
        node = Node(data)
        if self.root is None:
            self.root = node
        else:
            self.insertNode(self.root, node)

    def insertNode(self, root, node):
        if node.data <= root.data:
            if root.left is None:
                root.left = node
            else:
                self.insertNode(root.left, node)
        else:
            if root.right is None:
                root.right = node
            else:
                self.insertNode(root.right, node)

    def traverse(self):
        if self.root:
            self.inOrder(self.root)

    def inOrder(self, root):
        if root is None:
            return
        else:
            self.inOrder(root.left)
            print(root.data)
            self.inOrder(root.right)

    def getMax(self):
        if self.root :
            return self.findMaxValue(self.root)

    def findMaxValue(self,root):
        if root.right is None:
            return self.findMax(root.right)
        return root.data

    def getMin(self):
        if self.root:
            return self.findMaxValue(self.root)

    def findMinValue(self,root):
        if root.left:
            return self.findMin(root.left)
        return root.data

    def delete(self,data):
        if self.root:
            self.root = self.deleteNode(self.root,data)

    def deleteNode(self,root, data):
        if root is None:
            return root
        elif data <= root.data:
            root.left =  self.deleteNode(root.left,data)
        elif data > root.data:
            root.right = self.deleteNode(root.right,data)
        else:

            if root.right is None and root.left is None:
                del root
                return None
            elif root.left is None:
                tempNode = root.right
                del root
                return  tempNode
            elif root.right is None:
                tempNode = root.left
                del root
                return  tempNode
            else:
                tempdata = self.getPredecessor(root.left)
                root.data = data
                self.deleteNode(root.right,tempdata)
                return root

    def getPredecessor(self, root):
        if root.right:
            return self.getMin(root.right)
        return root

    def getSucceesor(self, root):
        pass


<file_sep>class Vertex(object):

    def __init__(self, data):
        self.data = data
        self.neighbours = []
        self.visited = False

    def addNeighbours(self, v):
        self.neighbours.append(v)
        self.neighbours.sort()

class Graph(object):

    def __init__(self):
        self.vertices = {}

    def addVertex(self, vertex):
        if isinstance(vertex, Vertex) and vertex not in self.vertices:
            self.vertices[vertex.data] = vertex
            return True
        return False

    def addEdge(self,v1, v2):
        if v1 in self.vertices and v2 in self.vertices:
            self.vertices[v1].addNeighbours(v2)
            self.vertices[v2].addNeighbours(v1)
            return True
        return False

    def print_graph(self):
        for key in sorted(list(self.vertices.keys())):
            print(key + " -> "+str(self.vertices[key].neighbours))

graph = Graph()
for i in range(ord("A"), ord("K")):
    graph.addVertex(Vertex(chr(i)))

edges = ['AB', 'AE', 'BF', 'CG', 'DE', 'DH', 'EH', 'FG', 'FI', 'FJ', 'GJ', 'HI']
for edge in edges:
    graph.addEdge(edge[:1],edge[1:])
graph.print_graph()<file_sep>class Node(object):

    def __init__(self, name):
        self.name = name
        self.neighbours = []
        self.visited = False

    def addNeighbours(self,node):
        self.neighbours.append(node)


class BreadthFirstSearch(object):


    def bfs(self,startNode):

        queue = []
        queue.append(startNode)
        startNode.visited = True
        while queue:
            actualNode = queue.pop(0)
            print(actualNode.name)

            for n in actualNode.neighbours:
                if not n.visited:
                    n.visited = True
                    queue.append(n)

node1 = Node("A")
node2 = Node("B")
node3 = Node("C")
node4 = Node("D")
node5 = Node("E")

node1.addNeighbours(node2)
node1.addNeighbours(node3)
node1.addNeighbours(node4)
node2.addNeighbours(node1)
node3.addNeighbours(node1)
node3.addNeighbours(node4)
node4.addNeighbours(node1)
node4.addNeighbours(node3)
node4.addNeighbours(node5)
node5.addNeighbours(node4)

bfs = BreadthFirstSearch()
bfs.bfs(node1)



<file_sep>INF = 100000
import heapq
class PriorityQueueMap(object):

    def __init__(self):
        self.eq = []
        self.eq_finder = {}

    def add(self, key, priority=INF):
        self.eq_finder[key] = priority
        heapq.heappush(self.eq, [priority,key])

    def getMin(self):
        minVertex = heapq.heappop(self.eq)[1]
        self.eq_finder.pop(minVertex)
        return minVertex

    def decrease(self,key, priority):
        previousPriority = self.eq_finder[key]
        self.eq_finder[key] = priority
        index = self.eq.index([previousPriority, key])
        del self.eq[index]
        heapq.heappush(self.eq,[priority,key])

class Edge(object):

    def __init__(self, startVertex, endVertex, weight):
        self.startVertex = startVertex
        self.endVertex = endVertex
        self.weight = weight

class Vertex(object):

    def __init__(self,name):
        self.name = name
        self.neighbours = []
        self.visited = False
        self.edges = []

    def addNeighbour(self,v):
        self.neighbours.append(v)


class Graph(object):

    def __init__(self, numVertex):
        self.numberVertex = numVertex
        self.vertexs = {}
        self.edges = []

    def addVertex(self, name):
        vertex = Vertex(name)
        self.vertexs[name] = vertex

    def addEdge(self, u, v, w):
        edge = Edge(u,v,w)
        self.vertexs[u].addNeighbour(v)
        self.vertexs[v].addNeighbour(u)
        self.vertexs[u].edges.append(edge)
        self.vertexs[v].edges.append(edge)
        self.edges.append(edge)

    def DijkstraAlgorithm(self, sourceVertex = 0):
        vertexParent = {}
        vertexDistance = {}
        queue = PriorityQueueMap()
        for key in self.vertexs.keys():
            queue.add(key)
        queue.decrease(sourceVertex,0)
        vertexParent[sourceVertex] = None
        vertexDistance[sourceVertex] = 0

        while len(queue.eq_finder) > 0:
            currentVertex = queue.getMin()
            print("CurrentVertex ",currentVertex)
            for edge in self.vertexs[currentVertex].edges:
                print("Start vertex", edge.startVertex)
                print("End Vertex", edge.endVertex)
                print("Weight ",edge.weight)
                otherVertex = self.get_other_vertex_for_edge(currentVertex, edge)
                if not otherVertex in queue.eq_finder:
                    continue

                new_distance = int(edge.weight) + int(vertexDistance[currentVertex])
                if queue.eq_finder[otherVertex] > new_distance:
                    vertexParent[otherVertex] = currentVertex
                    vertexDistance[otherVertex] = new_distance
                    queue.decrease(otherVertex, new_distance)
        print(vertexParent)
        print(sorted(vertexDistance.items(), key=lambda s: s[0]))

    def get_other_vertex_for_edge(self, vertex, edge):
        if edge.startVertex == vertex:
            return edge.endVertex
        else:
            return edge.startVertex

graph = Graph(9)
for i in range(graph.numberVertex):
    graph.addVertex(i)
graph.addEdge(0,1,4)
graph.addEdge(0,7,8)
graph.addEdge(1,2,8)
graph.addEdge(1,7,11)
graph.addEdge(2,3,7)
graph.addEdge(2,8,2)
graph.addEdge(2,5,4)
graph.addEdge(3,4,9)
graph.addEdge(3,5,14)
graph.addEdge(4,5,10)
graph.addEdge(5,6,2)
graph.addEdge(6,7,1)
graph.addEdge(6,8,6)
graph.addEdge(7,8,7)

graph.DijkstraAlgorithm()




<file_sep>class BinaryNode(object):

    def __init__(self,data):
        self.data = data
        self.left = None
        self.right = None

    def getRight(self):
        return self.right

    def getLeft(self):
        return  self.left

    def setRight(self, right):
        self.right = right

    def setLeft(self, left):
        self.left = left

class BinarySearchTree(object):

    def __init__(self):
        self.root = None

    def getNewNode(self, data):
        new_node = BinaryNode(data)
        return new_node

    def insert(self, data):
        node = BinaryNode(data)
        if self.root is None:
            self.root = node
        else:
            self.insertNode(self, self.root, node)

    def insertNode(self, root, node):
        if node.data <= root.data:
            if root.left is None:
                root.left = node
            else:
                self.insertNode(root.left,node)
        elif node.data > root.data:
            if root.right is None:
                root.right = node
            else:
                self.insertNode(root.right, node)

    def searchKey(self, root, key):
        if root is None:
            return False
        elif root.data == key:
            return True
        elif key < root.data:
            return self.searchKey(root.left, key)
        elif key > root.data:
            return  self.searchKey(root.right, key)

    def inOrder(self,root):
        if root is None:
            return
        self.inOrder(root.left)
        print(root.data)
        self.inOrder(root.right)

    def findMin(self,root):
        if root is None:
            return -1
        else:
            if root.left is not None:
                return self.findMin(root.left)
            return root.data

    def findMax(self, root):
        if root is None:
            return -1
        else:
            if root.right is not None:
                return self.findMax(root.right)
            return root.data

    def findHeightTree(self, root):
        if root is None:
            return -1
        else:
            return max(self.findHeightTree(root.left),self.findHeightTree(root.right)) + 1


BST = BinarySearchTree()
node = BST.getNewNode(15)
BST.insertNode(BST.root,node)
node = BST.getNewNode(10)
BST.insertNode(BST.root,node)
node = BST.getNewNode(5)
BST.insertNode(BST.root,node)
node = BST.getNewNode(25)
BST.insertNode(BST.root,node)
node = BST.getNewNode(1)
BST.insertNode(BST.root,node)
node = BST.getNewNode(40)
BST.insertNode(BST.root,node)
node = BST.getNewNode(45)
BST.insertNode(BST.root,node)
node = BST.getNewNode(35)
BST.insertNode(BST.root,node)
node = BST.getNewNode(30)
BST.insertNode(BST.root,node)
node = BST.getNewNode(50)
BST.insertNode(BST.root,node)
print(BST.searchKey(BST.root, 50))
BST.inOrder(BST.root)
print(BST.findMin(BST.root))
print((BST.findMax(BST.root)))
print(BST.findHeightTree(BST.root))<file_sep>class Node(object):

    def __init__(self, data):
        self.data = data
        self.parent = None
        self.size = 1


class DisjointSet(object):

    def __init__(self):
        self.set = {}

    def makeSet(self,data):
        new_node = Node(data)
        new_node.parent = new_node
        self.set[data] = new_node

    def union(self,data1, data2):

        node1 = self.set[data1]
        node2 = self.set[data2]

        parent1 = self.findSetByCompression(node1)
        parent2 = self.findSetByCompression(node2)

        if parent1.data == parent2.data:
            return
        else:
            if parent1.size >= parent2.size:
                parent2.parent = parent1
                parent1.size = parent1.size + parent2.size
            else:
                parent1.parent = parent2
                parent2.size = parent2.size + parent1.size

    def findSetByCompression(self,node):
        if node.parent == node:
            return node
        else:
            node.parent = self.findSetByCompression(node.parent)
            return node.parent

    def findSizeOfCommunity(self,data):
        return self.findSetByCompression(self.set[data]).size

ds = DisjointSet()
n,q = list(map(int,input().split()))
for i in range(1,n+1):
    ds.makeSet(i)
for _ in range(q):
    input_list = list(input().split())
    if input_list[0] == 'Q':
        print(ds.findSizeOfCommunity(int(input_list[1])))
    elif input_list[0] == 'M':
        ds.union(int(input_list[1]),int(input_list[2]))<file_sep>class Node(object):

    def __init__(self, data):
        self.data = data
        self.parent = None
        self.rank = 0

class DisjointSet(object):

    def __init__(self):
        self.setDict = {}

    def makeSet(self,data):
        new_node = Node(data)
        new_node.parent = new_node
        self.setDict[data] = new_node

    def union(self, parent1, parent2):

        if parent1.rank >= parent2.rank:
            parent2.parent = parent1
            parent1.rank = parent1.rank + 1 if parent1.rank == parent2.rank else parent1.rank
        else:
            parent1.parent = parent2


    def findSetByCompression(self,node):
        if node.parent == node:
            return node
        else:
            node.parent = self.findSetByCompression(node.parent)
            return node.parent

    def findSet(self,data):
        return self.findSetByCompression(self.setDict[data])


class Graph(object):

    def __init__(self, num):
        self.edgeList = []
        self.numberVertices = num

    def addEdge(self, u, v, w,):
        self.edgeList.append([u,v,w])

    def sortEdge(self):
        self.edgeList = sorted(self.edgeList,key=lambda l: l[2])

    def kruskalAlgorithm(self):
        added_edge_list = []
        ds = DisjointSet()

        for i in range(0,self.numberVertices):
            ds.makeSet(i)
        self.sortEdge()
        for arr in self.edgeList:
            parent1 = ds.findSet(arr[0])
            parent2 = ds.findSet(arr[1])

            if parent1 == parent2:
                continue
            else:
                ds.union(parent1,parent2)
                added_edge_list.append(arr)
        return added_edge_list


g = Graph(9)
g.addEdge(0,7,8)
g.addEdge(0,1,4)
g.addEdge(1,2,8)
g.addEdge(1,7,11)
g.addEdge(2,5,4)
g.addEdge(2,3,7)
g.addEdge(3,4,9)
g.addEdge(3,5,14)
g.addEdge(5,4,10)
g.addEdge(6,5,2)
g.addEdge(7,8,7)
g.addEdge(7,6,1)
g.addEdge(8,6,6)
g.addEdge(8,2,2)

print(g.kruskalAlgorithm())


<file_sep>class Evaluate(object):

    def __init__(self):
        self.stk = []
        self.top = None

    def pop(self):
        try:
            res = self.stk.pop()
            self.top = self.stk[-1]
        except IndexError:
            self.top = None
        return res

    def push(self,data):
        self.stk.append(data)
        self.top = self.stk[-1]

    def evaluatePostfix(self, expression):
        for char in expression:
            try:
                data = int(char)
            except ValueError:
                oper2 = self.pop()
                oper1 = self.pop()
                res = self.evaluateExpression(char,oper1, oper2)
                self.push(res)
            else:
                self.push(data)
        print(self.getTop())

    def evaluatePrefix(self,expression):
        for char in expression[::-1]:
            try:
                data = int(char)
            except ValueError:
                oper1 = self.pop()
                oper2 = self.pop()
                res = self.evaluateExpression(char, oper1, oper2)
                self.push(res)
            else:
                self.push(data)
        print(self.getTop())

    def evaluateExpression(self,operand, operator1, operator2):
        if operand == '*':
            return operator1 * operator2
        elif operand == '/':
            return operator1 // operator2
        elif operand == '+':
            return operator1 + operator2
        elif operand == '-':
            return operator1 - operator2

    def infixtopostfix(self,expression):
        pass

    def getTop(self):
        return self.top

evalexper = Evaluate()
evalexper.evaluatePostfix('23*54*+9-')
evalexper.evaluatePrefix('-+*23*549')
<file_sep>class Graph:

    def __init__(self, n):
        self.noOfVertex = n
        self.matrix = [[0 for _ in range(n)] for _ in range(n)]

    def addEdge(self, u,v):
        self.matrix[u-1][v-1] = 1
        self.matrix[v-1][u-1] = 1


    def dfs(self):
        pass

graph = Graph(6)
graph.addEdge(1,2)
graph.addEdge(1,3)
graph.addEdge(2,4)
graph.addEdge(4,5)
graph.addEdge(2,3)
graph.addEdge(6,1)
graph.addEdge(6,2)
print(graph.matrix)<file_sep>def reverse(str):
    if len(str) == 1:
        return str
    return reverse(str[1:]) + str[0]

print(reverse("Ravi"))

def permute(str):
    out = []
    if len(str) == 1:
        out = [str]
    else:
        for i,let in enumerate(str):
            for perm in permute(str[:i] + str[i+1:]):
                print(perm)
                out += [let+perm]
    return out



print(permute('abc'))<file_sep>class Heap(object):

    def __init__(self):
        self.heap = []
        self.size = 0



    def build_max_heap(self, arr):
        self.size = len(arr)
        self.heap = arr
        for i in range(self.size//2, -1,-1):
            self.max_heapify(i)

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

    def max_heapify(self, index):
        left = 2 * index + 1
        right = 2 * index +2
        largest = index
        if left < self.size and self.heap[largest] < self.heap[left]:
            largest = left
        if right < self.size and self.heap[largest] < self.heap[right]:
            largest = right

        if largest != index:
            self.swap(index,largest)
            self.max_heapify(largest)


    def heapSort(self, array):
        self.build_max_heap(array)
        for i in range(self.size-1,0,-1):
            self.swap(i,0)
            self.size -= 1
            self.max_heapify(0)


heap = Heap()
heap.heapSort([3,4,9,7,8,2,5,6,1])
print(heap.heap)<file_sep>class Node(object):

    def __init__(self, data):
        self.data = data
        self.next = None

    def setNext(self,next):
        self.next = next

    def setData(self, data):
        self.data = data

    def getNext(self):
        return self.next

    def getData(self):
        return self.data

class Queue(object):

    def __init__(self):
        self.top = None
        self.end = None

    def enqueue(self,data):
        new_node = Node(data)
        if self.top is None:
            self.top = new_node
        else:
            current = self.top
            while current.next is not None:
                current = current.next
            current.setNext(new_node)
        self.end = new_node

    def dequeue(self):
        self.top = self.top.next
        if self.top is None:
            self.end = None

    def getTop(self):
        return self.top

    def display(self):
        current = self.top
        while current is not None:
            print(current.data)
            current = current.next


q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(5)
q.enqueue(8)
q.enqueue(9)
q.dequeue()
q.display()<file_sep>class Node(object):

    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BinarySearchTree(object):

    def __init__(self):
        self.root = None

    def addData(self, data):
        new_node = Node(data)
        if self.root is None:
            self.root = new_node
        else:
            self.addUtil(self.root,new_node)

    def addUtil(self, startingNode, node):
        if node.data <= startingNode.data:
            if startingNode.left is None:
                startingNode.left = node
            else:
                self.addUtil(startingNode.left, node)
        else:
            if startingNode.right is None:
                startingNode.right = node
            else:
                self.addUtil(startingNode.right, node)

    def searchkey(self,key, node):
        if node is None:
            return False
        if node.data == key:
            return True
        else:
            if node.data < key:
                self.searchkey(key, node.right)
            else:
                self.searchkey(key, node.left)

    def getMax(self, node):
        if node.right is None:
            return node.data
        else:
            self.getMax(node.right)

    def getMin(self, node):
        if node.left is None:
            return node.data
        else:
            self.getMin(node.left)

    def getLowestCommonAncestor(self,data1,data2, node):
        if node.data > data1 and node.data > data2:
            self.getLowestCommonAncestor(data1, data2, node.left)
        elif node.data < data1 and node.data < data2:
            self.getLowestCommonAncestor(data1, data2, node.right)
        else:
            print(node.data)

    def inOrder(self, node):
        if node is None:
            return
        else:
            self.inOrder(node.left)
            print(node.data)
            self.inOrder(node.right)

    def checkBST(self):
        return self.checkBSTUtil(self.root, -1400, 1400)

    def checkBSTUtil(self, node, min, max):
        if node is None:
            return True
        else:
            if min <= node.data and node.data > max:
                return False
            return (self.checkBSTUtil(node.left, min, node.data) and self.checkBSTUtil(node.right, node.data, max))

BST = BinarySearchTree()
BST.addData(10)
BST.root.left = Node(24)
BST.root.right = Node(25)
print(BST.checkBST())
'''
BST.addData(10)
BST.addData(-10)
BST.addData(30)
BST.addData(25)
BST.addData(60)
BST.addData(28)
BST.addData(78)
print(BST.checkBST())
'''
<file_sep>import heapq
INF = 1000000

class PriorityQueueMap(object):
    def __init__(self):
        self.eq = []
        self.entry_finder = {}

    def add(self, key, prioprity = INF):
        if key in self.entry_finder:
             raise KeyError("Key already exists")
        self.entry_finder[key] = prioprity
        heapq.heappush(self.eq,[prioprity, key])

    def delete(self, task):
        if not task in self.entry_finder:
            raise KeyError("Key doesnt exist")
        self.entry_finder.pop(task)

    def getMin(self):
        minVertex = heapq.heappop(self.eq)[1]
        self.entry_finder.pop(minVertex)
        return minVertex

    def descrease(self, key, priority):
        previousPriority = self.entry_finder[key]
        self.entry_finder[key] = priority
        index = self.eq.index([previousPriority, key])
        del self.eq[index]
        heapq.heappush(self.eq,[priority, key])

class Edge(object):

    def __init__(self, vertex1, vertex2, weight ):
        self.startingVertex = vertex1
        self.endVertex = vertex2
        self.weight = weight

class Vertex(object):
    def __init__(self, data):
        self.name = data
        self.adjanceyList = []
        self.visited = False
        self.edges = []

    def addNeighbours(self,edge, neighbour):
        self.adjanceyList.append(neighbour)
        self.edges.append(edge)

    def getEdge(self):
        return self.edges

class Graph():

    def __init__(self):
        self.vertexList = {}
        self.edgeList = {}

    def addEdge(self,u,v,w):
        edge = Edge(u,v,w)
        self.edgeList[u+v] = edge
        self.vertexList[u].addNeighbours(edge, v)
        self.vertexList[v].addNeighbours(edge, u)

    def addVertex(self,data):
        self.vertexList[data] = Vertex(data)

    def PrimsAlgorithm(self, startVertex):
        resultEdge = []
        vertexEdge = {}

        queue = PriorityQueueMap()
        for key in self.vertexList.keys():
            queue.add(key)
        queue.descrease(startVertex, 0)
        
        while len(queue.entry_finder) > 0:
            vertex = queue.getMin()
            if vertex in vertexEdge:
                resultEdge.append(vertexEdge[vertex])
            for edge in self.vertexList[vertex].edges:
                adjacent = self.get_other_vertex_for_edge(vertex,edge)
                if adjacent in queue.entry_finder and edge.weight <  queue.entry_finder[adjacent]:
                    queue.descrease(adjacent, edge.weight)
                    vertexEdge[adjacent] = edge.startingVertex + edge.endVertex
        print(resultEdge)

    def get_other_vertex_for_edge(self ,vertex, edge):
        if edge.startingVertex == vertex:
            return edge.endVertex
        else:
            return edge.startingVertex


graph = Graph()
for i in range(ord("A"), ord("G")):
    graph.addVertex(chr(i))
graph.addEdge("A","D",1)
graph.addEdge("A","B",3)
graph.addEdge("B","D",3)
graph.addEdge("B","C",1)
graph.addEdge("C","E",5)
graph.addEdge("C","D",1)
graph.addEdge("C","F",4)
graph.addEdge("D","E",6)
graph.addEdge("F","E",2)
graph.PrimsAlgorithm("A")

<file_sep>class BalanacedParentheses(object):

    def __init__(self):
        self.stk = []
        self.top = None

    def pop(self):
        self.stk.pop()
        try:
            self.top = self.stk[-1]
        except IndexError:
            self.top  = None

    def push(self,data):
        self.stk.append(data)
        self.top = self.stk[-1]


    def balancedParantheses(self, string):
        for para in string:
            if para == '(' or para =='{' or para == '[':
                self.push(para)
            elif para == '}' or para == ')' or para == ']':
                if self.arePair(self.top, para):
                    self.pop()
                else:
                    return False
        return self.isEmpty()


    def arePair(self,opening, closing):
        return(
                opening == '(' and closing == ')'
            or opening == '[' and closing == ']'
            or opening == '{' and closing == '}'
        )

    def isEmpty(self):
        return len(self.stk) == 0

#stk = BalanacedParentheses()
#print(stk.balancedParantheses(input()))

import sys


class Stack(object):
    def __init__(self):
        self.stk = []
        self.top = None

    def push(self, data):
        self.stk.append(data)
        self.top = self.stk[-1]

    def pop(self):
        try:
            self.stk.pop()
            self.top = self.stk[-1]
        except IndexError:
            self.top = None

    def isEmpty(self):
        return len(self.stk) == 0

    def isClosingPair(self, opening, close):
        return (
            opening == '(' and close == ')' or
            opening == '{' and close == '}' or
            opening == '[' and close == ']'
        )

    def balancedParanthese(self, expression):
        for para in expression:
            if para in ['(', '{', '[']:
                self.push(para)
            elif para in [')', '}', ']']:
                if self.isClosingPair(self.top, para):
                    self.pop()
                else:
                    return 'NO'
        else:
            if self.isEmpty():
                return 'YES'
            else:
                return 'NO'



t = int(input().strip())
for a0 in range(t):
    s = input().strip()
    stack = Stack()
    print(stack.balancedParanthese(s))<file_sep>class Heap(object):

    def __init__(self):
        self.arr = []
        self.heap_size = 0

    def build_max_heap(self):
        length = (len(self.arr) // 2)
        while length > 0:
            self.max_heapify(length)
            length -= 1


    def max_heapify(self, i):
        l = self.left(i)
        r = self.right(i)
        largest = self.arr[i]
        if l > largest:
            largest = l
        if r > largest:
            largest = r
        l_index = self.arr.index(largest)
        if l_index != i:
            (self.arr[i],self.arr[l_index]) = (self.arr[l_index],self.arr[i])
            self.max_heapify(l_index)

    def min_heapify(self,i):
        l = self.left(i)
        r = self.right(i)
        smallest = self.arr[i]
        if self.arr.index(l) <= self.heap_size and l < smallest:
            smallest = l
        if self.arr.index(r) <= self.heap_size < smallest:
            smallest = r
        l_index = self.arr.index(smallest)
        if l_index != i:
            self.arr[i],self.arr[l_index] = self.arr[l_index],self.arr[i]
            self.min_heapify(l_index)

    def right(self,i):
        if i == 0:
            return self.arr[1]
        try:
            return self.arr[2*i]
        except IndexError:
            return 0

    def left(self,i):
        if i == 0:
            return self.arr[2]
        try:
            return self.arr[2*i + 1]
        except IndexError:
            return 0

    def setArr(self,arr):
        self.arr = arr
        self.heap_size = len(self.arr)

    def HeapSort(self):
        l = []
        self.build_max_heap()
        length = len(self.arr)
        for i in range(length-1, 2,-1):
            self.arr[i],self.arr[1] = self.arr[1],self.arr[i]
            l.append(self.arr.pop())
            self.heap_size -= 1
            self.max_heapify(1)
        l.extend(self.arr[1:])
        self.arr = l[::-1]


heap = Heap()
heap.setArr([0,4,1,3,2,16,9,10,14,8,7])
heap.HeapSort()
print(heap.arr)<file_sep>class Node(object):

    def __init__(self,name):
        self.name = name
        self.parent = None
        self.size = 1

    def setParent(self, parent):
        self.parent = parent

    def getParent(self):
        return  self.parent

<file_sep>class Node(object):

    def __init__(self,data, next = None, previous = None):
        self.data = data
        self.next = next
        self.previous = previous

    def setData(self, data):
        self.data = data

    def setPrevious(self, previous):
        self.previous = previous

    def setNext(self, next):
        self.next = next

    def getData(self):
        return  self.data

    def getNext(self):
        return self.next

    def getPrevious(self):
        return  self.previous

class DoubleLinkedList(object):

    def __init__(self):
        self.head = None
        self.count = 0

    def addNodeAtEnd(self, data):
        new_node = Node(data)
        if self.count == 0:
            self.head = new_node
        else:
            current = self.head
            while current.getNext() is not None:
                current = current.getNext()
            current.setNext(new_node)
            new_node.setPrevious(current)
        self.count += 1

    def addNodeAtStart(self,data):
        new_node = Node(data)
        if self.count == 0:
            self.head = new_node
        else:
            current = self.head
            current.setPrevious(new_node)
            new_node.setNext(current)
            self.head = new_node
        self.count += 1


    def addNodeAtPosition(self,data,position):
        if position > self.count or position < 0:
            print('Print Invalid Position')
        else:
            if position == self.count:
                self.addNodeAtEnd(data)
            elif position == 1:
                self.addNodeAtStart(data)
            else:
                current = self.head
                new_node = Node(data)
                current_position = 1

                while current_position != position:
                    current = current.getNext()
                    current_position += 1

                next = current.getNext() #Getting next node
                current.setNext(new_node) #setting current->next = new_node
                new_node.setPrevious(current) #setting new_node->previous = current
                new_node.setNext(next) #setting new_node -> next = next
                next.setPrevious(new_node) #next->previous = new_node
            self.count+=1



    def deleteNodeAtStart(self):
        if self.count == 0:
            print('List Is Empty')
        else:
            current = self.head
            next = current.getNext()
            current.setNext(None)
            next.setPrevious(None)
            self.head = next
            self.count -= 1


    def deleteNodeAtEnd(self):
        if self.count == 0:
            print('List is empty')
        else:
            current = self.head
            while current.getNext() is not None:
                current = current.getNext()
            previous = current.getPrevious()
            current.setPrevious(None)
            previous.setNext(None)
            self.count -= 1

    def deleteNodeAtPosition(self, position):
        if position > self.count or position < 1:
            print('Invalid position')
        elif position == self.count:
            self.deleteNodeAtEnd()
        elif position == 1:
            self.deleteNodeAtStart()
        else:
            current = self.head
            current_position = 1
            while current_position != position:
                current = current.getNext()
                current_position += 1
            previous = current.getPrevious()
            next = current.getNext()
            previous.setNext(next)
            next.setPrevious(previous)
            current.setPrevious(None)
            current.setNext(None)
        self.count -= 1


    def reverseDoubleLinkedList(self):
        if self.count == 0:
            return
        else:
            current = self.head
            while current is not None:
                previous = current.getPrevious()
                next = current.getNext()
                current.setPrevious(next)
                current.setNext(previous)
                previous = current
                current = next
            self.head = previous

    def printAllNode(self):
        current = self.head
        while current != None:
            print('---------------------------------')
            print('Data {0}'.format(current.getData()))
            print('Current {0}'.format(current))
            print('Previous {0}'.format(current.getPrevious()))
            print('Next {0}'.format(current.getNext()))
            print('---------------------------------')
            current = current.getNext()

    def getCount(self):
        return self.count

    def PrintReverse(self, head):
        if head is None:
            return
        self.PrintReverse(head.next)
        print(head.data)

d = DoubleLinkedList()
d.addNodeAtEnd(12)
d.addNodeAtEnd(13)
d.addNodeAtEnd(15)
d.addNodeAtEnd(19)
d.addNodeAtStart(10)
d.addNodeAtPosition(14,3)
d.printAllNode()
d.deleteNodeAtStart()
d.deleteNodeAtEnd()
d.deleteNodeAtPosition(2)
d.printAllNode()
d.reverseDoubleLinkedList()
d.printAllNode()<file_sep>class Vertex(object):

    def __init__(self, name):
        self.name = name
        self.neighbours = []
        self.visited = False

    def addNeighbours(self, vertex):
        self.neighbours.append(vertex)

class Graph(object):

    def __init__(self):
        self.vertices = {}

    def addVertex(self, vertex):
        if isinstance(vertex, Vertex) and vertex not in self.vertices:
            self.vertices[vertex.name] = vertex
            return True
        return False

    def addEdge(self,u,v):
        self.vertices[u].addNeighbours(self.vertices[v])

    def DFS(self,v):
        v.visited = True
        print(v.name)
        for vertex in v.neighbours:
            if not vertex.visited:
                self.DFS(vertex)

    def TopologicalUtil(self, vertex, sorted):
        if not vertex.visited:
            vertex.visited = True

        for v in vertex.neighbours:
            if not v.visited:
                self.TopologicalUtil(v,sorted)

        sorted.append(vertex.name)


    def TopologicalSort(self):
        sorted = []
        for key in self.vertices.keys():
            if not self.vertices[key].visited:
                self.TopologicalUtil(self.vertices[key],sorted)

        print(sorted)


graph = Graph()
graph = Graph()
for i in range(ord("A"), ord("I")):
    graph.addVertex(Vertex(chr(i)))

edges = ['AC', 'BC', 'BD', 'CE', 'DF', 'EH', 'EF', 'FG',]
for edge in edges:
    graph.addEdge(edge[:1],edge[1:])
graph.TopologicalSort()<file_sep>class BinaryTreeNode(object):

    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def setLeft(self,left):
        self.left = left

    def setRight(self,right):
        self.right = right

    def getLeft(self):
        return self.left

    def getRight(self):
        return self.right

    def getData(self):
        return self.data


class BinaryTree(object):

    def __init__(self):
        self.root = None

    def getNewNode(self,data):
        new_node = BinaryTreeNode(data)
        return new_node

    def InsertNode(self, root, node):
        if root is None:
            self.root = node
        else:
            if root.data > node.data:
                if root.left is None:
                    root.left = node
                else:
                    self.InsertNode(root.left, node)
            elif root.data < node.data:
                if root.right is None:
                    root.right = node
                else:
                    self.InsertNode(root.right, node)

    def SearchNode(self,root, key):
        if root is None:
            return False
        elif root.data == key:
            return True
        elif key < root.data:
            return self.SearchNode(root.left, key)
        elif key > root.data:
            return self.SearchNode(root.right, key)

    def getMin(self,root):
        if root.left is None:
            return root.data
        else:
            return self.getMin(root.left)

    def getMax(self,root):
        if root.right is None:
            return root.data
        else:
            return self.getMax(root.right)

    def FindHeight(self, root):
        if root is None:
            return -1
        return max(self.FindHeight(root.left), self.FindHeight(root.right)) + 1

    def leveorder(self):
        if self.root is None:
            return
        else:
            l = []
            l.append(self.root)
            while len(l) != 0:
                node = l.pop(0)
                print(node.data)
                if node.left is not None:
                    l.append(node.left)
                if node.right is not None:
                    l.append(node.right)

    def preorder(self,root):
        if root is None:
            return
        print(root.data)
        self.preorder(root.left)
        self.preorder(root.right)

    def inorder(self, root):
        if root is None:
            return
        self.inorder(root.left)
        print(root.data)
        self.inorder(root.right)

    def postorder(self, root):
        if root is None:
            return
        self.postorder(root.left)
        self.postorder(root.right)
        print(root.data)



BT  = BinaryTree()
node = BT.getNewNode(15)
BT.InsertNode(BT.root,node)
node = BT.getNewNode(20)
BT.InsertNode(BT.root,node)
node = BT.getNewNode(30)
BT.InsertNode(BT.root,node)
node = BT.getNewNode(5)
BT.InsertNode(BT.root,node)
node = BT.getNewNode(10)
BT.InsertNode(BT.root,node)
node = BT.getNewNode(25)
BT.InsertNode(BT.root,node)
node = BT.getNewNode(28)
BT.InsertNode(BT.root,node)
node = BT.getNewNode(45)
BT.InsertNode(BT.root,node)
#print(BT.getMin(BT.root))
#print(BT.getMax(BT.root))
#print(BT.SearchNode(BT.root,45))
#print(BT.FindHeight(BT.root))
#BT.leveorder()
BT.preorder(BT.root)
BT.inorder(BT.root)
BT.postorder(BT.root)<file_sep>class Node(object):

    def __init__(self,data):
        self.key = data
        self.right = None
        self.left = None
        self.parent = None


class BST(object):

    def __init__(self):
        self.root = None

    def insert(self,data):
        node = Node(data)
        if self.root is None:
            self.root = node
            self.root.parent = self.root
        else:
            self.insertNode(self.root,node)

    def insertNode(self, root, node):
        if node.key <= root.key:
            if root.left is None:
                root.left = node
                node.parent = root
            else:
                self.insertNode(root.left, node)
        else:
            if root.right is None:
                root.right = node
                node.parent = root
            else:
                self.insertNode(root.right, node)

    def getMinTree(self):
        if self.root is None:
            return self.root
        else:
            return self.getMin(self.root)


    def getMin(self, root):
        if root.left is not None:
            return self.getMin(root.left)
        return root

    def getMaxTree(self):
        if self.root is None:
            return self.root
        else:
            return self.getMax(self.root)

    def getMax(self, root):
        if root.right:
            return self.getMax(root.right)
        return root

    def successor(self, root):
        if root.right:
            return self.getMin(root.right)
        y = root.parent
        while y is not None and root == y.right:
            root = y
            y = y.parent
        return y

    def predecessor(self, root):
        if root.left:
            return self.getMax(root.left)
        y = root.parent
        while y is not None and root == y.left:
            root = y
            y = y.parent
        return y


    def delete(self, data):
        if self.root:
            self.root = self.removeNode(self.root, data)

    def removeNode(self, root, data):
        if root is None:
            return root
        elif data < root.key:
            root.left = self.removeNode(root.left, data)
        elif data > root.key:
            root. right = self.removeNode(root.right, data)
        else:
            if root.right is None and root.left is None:
                del root
                return None
            elif root.right is None:
                tempNode = root.left
                del root
                return tempNode
            elif root.left is None:
                tempNode = root.right
                del root
                return tempNode
            else:
                tempNode = self.successor(root)
                root.key = tempNode.key
                root.right = self.removeNode(root.right,tempNode.key)
        return root

    def traverse(self):
        if self.root is not None:
            self.traverseInOrder(self.root)

    def traverseInOrder(self, root):
        if root is None:
            return
        else:
            self.traverseInOrder(root.left)
            print(root.key)
            self.traverseInOrder(root.right)

    def heightOfTree(self, root):
        if root is None:
            return -1
        return max(self.heightOfTree(root.left), self.heightOfTree(root.right)) + 1

tree = BST()
tree.insert(15)
tree.insert(6)
tree.insert(18)
tree.insert(3)
tree.insert(7)
tree.insert(17)
tree.insert(20)
tree.insert(2)
tree.insert(4)
tree.insert(13)

#tree.insert(9)
#print(tree.root.key)
tree.traverse()
#node = tree.successor()
#print(node.key)
tree.delete(6)
print('-----------')
print('')
tree.traverse()
node = tree.predecessor(tree.root)
print(node.key)
#for _ in range(int(input())):
#    user_oper = list(map(int,input().split()))
#    if user_oper[0] == 1: # insert new node in tree
#        tree.insert(int(user_oper[1]))
#    elif user_oper[0] == 2: # delete node in tree
#        tree.delete()
#    elif user_oper[0] == 3: # get the Min of Tree
#        tree.getMinTree()
#    elif user_oper[0] == 4: #get the Max of Tree
#        tree.getMaxTree()
#    elif user_oper[0] == 5: #get the Successor of tree
#        tree.successor(tree.root)
#    elif user_oper[0] == 6:
#        node = tree.successor(tree.root)
#        print(node.data)
#    elif user_oper[0] == 7:
#        tree.traverse()



<file_sep>def rec_sum(n):

    if n == 0:
        return 0
    else:
        return n + rec_sum(n-1)

print(rec_sum(5))

def sum_func(n):
    if n < 1:
        return 0
    else:
        return n%10 + sum_func(n//10)

print(sum_func(4321))


def word_split(phrase,list_of_words, output = None):

    if output is None:
        output = []
    for word in list_of_words:
        if phrase.startwith(word):
            output.append(word)
            return  word_split(phrase[len(word):],list_of_words, output)
    return output<file_sep>class Node(object):

    def __init__(self, data):
        self.data = data
        self.next = None

    def setNext(self,next):
        self.next = next

    def setData(self,data):
        self.data = data

    def getData(self):
        return self.data

    def getNext(self):
        return self.next


class Stack(object):

    def __init__(self, limit = 10):
        self.limit = limit
        self.top = None
        self.count = 0

    def push(self, data):
        if self.isFull():
            print('Stack is Overflow')
            return
        else:
            new_node = Node(data)
            if self.top is not None:
                new_node.next = self.top
            self.top = new_node
            self.count += 1

    def pop(self):
        if self.isEmpty():
            print('Stack is empty')
        else:
            next = self.top.next
            self.top.next = None
            self.top = next
            self.count -= 1

    def getTop(self):
        return self.top.getData()

    def isFull(self):
        return self.count == self.limit

    def isEmpty(self):
        return self.count == 0

    def display(self):
        current = self.top
        while current is not None:
            print(current.getData())
            current = current.getNext()


stklinked = Stack()
stklinked.push(10)
stklinked.push(9)
stklinked.push(11)
stklinked.push(15)
stklinked.pop()
stklinked.pop()
stklinked.pop()
stklinked.pop()
stklinked.pop()<file_sep>class Node(object):

    def __init__(self,data):
        self.data = data
        self.parent = None
        self.rank = 0

class DisjointSet(object):

    def __init__(self):
        self.set = {}

    def makeSet(self, data):
        new_node = Node(data)
        new_node.parent = new_node
        self.set[data] = new_node

    def union(self, data1, data2):
        node1 = self.set[data1]
        node2 = self.set[data2]

        parent1 = self.findSetByCompersion(node1)
        parent2 = self.findSetByCompersion(node2)

        if parent1.data == parent2.data:
            return
        else:
            if parent1.rank >= parent2.rank:
                parent2.parent = parent1
                parent1.rank = parent1.rank + 1 if parent1.rank == parent2.rank else parent1.rank
            else:
                parent1.parent = parent2


    def findSetByCompersion(self,node):
        if node.parent == node:
            return node
        else:
            node.parent = self.findSetByCompersion(node.parent)
            return node.parent

    def findSet(self, data):
        return self.findSetByCompersion(self.set[data]).data

ds = DisjointSet()
for i in range(1,8):
    ds.makeSet(i)

ds.union(1, 2)
ds.union(2, 3)
ds.union(4, 5)
ds.union(6, 7)
ds.union(5, 6)
ds.union(3, 7)

for key in ds.set.keys():
    print(ds.findSet(key))

<file_sep>class Node(object):

    def __init__(self, data = None, color = None, parent = None,left = None, right = None):
        self.data = data
        self.parent = parent
        self.color = color
        self.left = left
        self.right = right


class RedBlackTree(object):

    def __init__(self):
        self.root = None

    def createNilNode(self):
        node = Node()
        node.color = "B"
        return node

    def createNode(self,data):
        node = Node()
        node.data = data
        node.color = "R"
        return node

    def leftRotate(self, node):
        pass

    def rightRotate(self, node):
        pass

    def insert(self,data):
        node = self.createNode(data)
        if self.root is None:
            self.root = node
            self.root.color = "B"
            self.root.right = self.createNilNode()
            self.root.left = self.createNilNode()
        else:
            self.root = self.insertNode(self.root, node)

    def insertNode(self,root,node):
        if node.data <= root.data:
            if root.left.data is None:
                root.left = node
                node.parent = root
            else:
                root.left = self.insertNode(root.left,node)
        else:
            if root.right.data is None:
                root.right = node
                node.parent = root
            else:
                root.right = self.insertNode(root.right, node)
        return root

    def inOrderTraversal(self,root):
        if root is None:
            return
        self.inOrderTraversal(root.left)
        print(root.data)
        self.inOrderTraversal(root.right)

    def getUncle(self,root):
        if root =

    def predecessor(self,root):
        pass

    def successor(self,root):
        pass

    def heightOfTree(self,root):
        pass


tree = RedBlackTree()
tree.insert(10)
tree.insert(-10)
tree.insert(20)
tree.inOrderTraversal(tree.root)
<file_sep>#PNR 8357948831, 2658321936
class Node(object):
    def __init__(self):
        self.data = None
        self.next = None

    def setData(self, data):
        self.data = data

    def setNext(self, next):
        self.next = next

    def getData(self):
        return self.data

    def getNext(self):
        return self.next

    def hasNext(self):
        return self.next == None

class LinkedList(object):

    def __init__(self):
        self.head = None
        self.count = 0

    def addNodeAtEnd(self, data):
        newNode = Node()
        newNode.setData(data)
        if self.head is None:
            self.head = newNode
        else:
            current = self.head
            while current.next != None:
                current = current.getNext()
            current.setNext(newNode)
        self.count += 1

    def addNodeAtStart(self,data):
        newNode = Node()
        newNode.setData(data)
        if self.head is None:
            self.head = newNode
        else:
            newNode.setNext(self.head)
            self.head = newNode

    def addNodeAtPosition(self,data,position):
        if position > self.count or position < 0:
            return None
        else:
            if position == self.count:
                self.addNodeAtEnd(data)
            elif position == 0:
                self.addNodeAtStart(data)
            else:
                newNode = Node()
                newNode.setData(data)
                current = self.head
                currentPosition = 1
                while position != currentPosition:
                    current = current.getNext()
                    currentPosition += 1
                temp = current.getNext()
                current.setNext(newNode)
                newNode.setNext(temp)
            self.count += 1

    def deleteNodeAtStart(self):
        if self.count == 0:
            print('The list is empty')
        else:
            self.head = self.head.getNext()
            self.count -= 1

    def deleteNodeAtEnd(self):
        if self.count == 0:
            print('The list is empty')
        else:
            currentNode = self.head
            previousNode = self.head
            while currentNode.next is not None:
                previousNode = currentNode
                currentNode = currentNode.getNext()
            currentNode.setNext(None)
            previousNode.setNext(None)
            self.count -= 1

    def deleteNodeAtPosition(self, position):
        if position > self.count or position < 0:
            print('Invalid Position')
        else:
            if position == 1:
                self.deleteNodeAtStart()
            elif position == self.count:
                self.deleteNodeAtEnd()
            else:
                currentPosition = 1
                previous= self.head
                current = self.head
                while currentPosition != position:
                    previous = current
                    current = current.getNext()
                temp = current.getNext()
                previous.setNext(temp)
                current.setNext(None)
                self.count -= 1


    def LinkedListInReverse(self):
        pass

    def reverseLinkedList(self):
        if self.count == 0:
            print('The list is empty')
        elif self.count == 1:
            return None
        else:
            current = self.head
            previous = None
            while current is not None:
                next = current.getNext()
                current.setNext(previous)
                previous = current
                current = next
            self.head = previous

    def printAllNode(self):
        current = self.head
        while current is not None:
            print("Current Location " , current)
            print("Current Next ",current.getNext())
            print("Current Data ",current.getData())
            current = current.getNext()


    def getCount(self):
        return self.count

    def PrintReverse(self, head):
        if head is None:
            return
        self.PrintReverse(head.next)
        print(head.data)

    def reverse(self, p):
        if p.next is None:
            self.head = p
            return
        self.reverse(p.next)
        next_node = p.next
        next_node.next = p
        p.next = None

    def RemoveDuplicates(self):
        head = self.head
        if head is None:
            return
        current = head
        while current.next is not None:
            next = current.next
            if current.data == next.data:
                temp = next.next
                current.next = temp
                current = current.next
        return head

newLinkedList = LinkedList()
newLinkedList.addNodeAtEnd(4)
newLinkedList.addNodeAtEnd(8)
newLinkedList.addNodeAtEnd(0)
newLinkedList.addNodeAtStart(10)
newLinkedList.addNodeAtPosition(25,2)
#newLinkedList.addNodeAtPosition(23,3)
#newLinkedList.printAllNode()
#print('')
#newLinkedList.deleteNodeAtEnd()
#newLinkedList.printAllNode()
#print('')

#newLinkedList.deleteNodeAtStart()
#newLinkedList.printAllNode()
#print('')

#newLinkedList.deleteNodeAtPosition(3)
#newLinkedList.printAllNode()

#newLinkedList.reverseLinkedList()
#print('')
#newLinkedList.printAllNode()
newLinkedList.printAllNode()<file_sep>class Node(object):

    def __init__(self,data):
        self.data = data
        self.next = None

    def getNext(self):
        return self.next

    def getData(self):
        return self.data

    def setNext(self, next):
        self.next = next

    def setData(self, data):
        self.data = data


class CircularSinglyLinkedList(object):

    def __init__(self):
        self.head = None
        self.count = 0

    def addNodeAtStart(self, data):
        new_node = Node(data)
        if self.count == 0:
            new_node.setNext(new_node)
        else:
            current = self.head
            while current.getNext() != self.head:
                current = current.getNext()
            current.setNext(new_node)
            new_node.setNext(self.head)
        self.head = new_node
        self.count += 1


    def addNodeAtEnd(self,data):
        new_node = Node(data)
        if self.count == 0:
            self.head = new_node
            new_node.setNext(new_node)
        else:
            current = self.head
            while current.getNext() != self.head:
                current = current.getNext()
            current.setNext(new_node)
            new_node.setNext(self.head)
        self.count += 1

    def addNodeAtPosition(self,data,position):
        if  position > self.count or position < 1:
            print('Invalid position')
            return
        elif position == self.count:
            self.addNodeAtEnd(data)
        elif position == 1:
            self.addNodeAtStart(data)
        else:
            new_node = Node(data)
            current = self.head
            current_position = 1
            while current_position != position:
                current = current.getNext()
                current_position += 1
            next = current.getNext()
            current.setNext(new_node)
            new_node.setNext(next)
        self.count += 1

    def deleteNodeAtStart(self):
        if self.count == 0:
            print('List is empty')
            return
        else:
            current = self.head
            while current.getNext() != self.head:
                current = current.getNext()
            next = self.head.getNext()
            current.setNext(next)
            self.head = next
            self.count -= 1

    def deleteNodeAtEnd(self):
        if self.count == 0:
            print('List is empty')
        else:
            current = self.head
            while current.getNext() != self.head:
                previous = current
                current = current.getNext()
            previous.setNext(self.head)
            current.setNext(None)
            self.count -= 1


    def deleteNodeAtPosition(self, position):
        if position > self.count or position < 1:
            print('Invalid position')
        elif position == self.count:
            self.deleteNodeAtEnd()
        elif position == 1:
            self.deleteNodeAtStart()
        else:
            current = self.head
            current_position = 1
            while current_position != position:
                previous = current
                current = current.getNext()
                current_position += 1
            next = current.getNext()
            previous.setNext(next)
            current.setNext(None)
            self.count -= 1

    def printAllNode(self):
        current = self.head
        count = 1
        while count <= self.count:
            print('---------------------------------')
            print('Data {0}'.format(current.getData()))
            print('Current {0}'.format(current))
            #print('Previous {0}'.format(current.getPrevious()))
            print('Next {0}'.format(current.getNext()))
            print('---------------------------------')
            current = current.getNext()
            count += 1



cll = CircularSinglyLinkedList()
cll.addNodeAtStart(10)
cll.addNodeAtEnd(12)
cll.addNodeAtEnd(14)
cll.addNodeAtEnd(19)
cll.addNodeAtStart(9)
cll.addNodeAtPosition(15,4)
#cll.printAllNode()
cll.deleteNodeAtStart()
#cll.printAllNode()
cll.deleteNodeAtEnd()
#cll.printAllNode()
cll.deleteNodeAtPosition(3)
cll.printAllNode()
<file_sep>class Stack(object):

    def __init__(self):
        self.stk = []
        self.top = None

    def push(self,data):
        self.stk.append(data)
        self.top = self.stk[-1]

    def pop(self):
        res = self.stk.pop()
        self.top = self.stk[-1]
        return res


stack = Stack()
for char in input().split():
    stack.push(char)

stack.pop()
<file_sep>import sys


class Node(object):
    def __init__(self, name):
        self.name = name
        self.parent = None
        self.rank = 0


class DisjointSet(object):
    def __init__(self):
        self.setdict = {}

    def makeSet(self, data):
        new_node = Node(data)
        new_node.parent = new_node
        self.setdict[data] = new_node

    def union(self, data1, data2):
        node1 = self.setdict[data1]
        node2 = self.setdict[data2]

        parent1 = self.findByCompression(node1)
        parent2 = self.findByCompression(node2)

        if parent1 == parent2:
            return False
        else:
            if parent1.rank >= parent2.rank:
                parent2.parent = parent1
                parent1.rank = parent1.rank + 1 if parent1.rank == parent2.rank else parent1.rank
            else:
                parent1.parent = parent2
            return True

    def findByCompression(self, node):

        if node.parent == node:
            return node
        else:
            node.parent = self.findByCompression(node.parent)
            return node.parent

    def find(self, data):
        return self.findByCompression(self.setdict[data]).name


class City(object):

    def __init__(self, numberCity, noOfRoad, costLibrary, costRoad):
        self.numberCity = numberCity
        self.edges = []
        self.costRoad = costRoad
        self.costLibrary = costLibrary
        self.noOfRoad = noOfRoad

    def calculateCostofLibrary(self, numberCity):
        return self.costLibrary * numberCity

    def calculateNoOfRoad(self):
        count = 0
        ds = DisjointSet()
        for i in range(1, self.numberCity + 1):
            ds.makeSet(i)
        for edge in self.edges:
            if ds.union(edge[0], edge[1]):
                count += 1
        return count

    def addEdge(self, startingVertex, endVertex):
        self.edges.append([startingVertex, endVertex])

    def totalCost(self):
        noOFtotalroad = self.numberCity - 1
        actualRoadBuild = self.calculateNoOfRoad()
        noOfLibaray = noOFtotalroad - actualRoadBuild
        totalCostOfroad = self.calculateCostofLibrary(noOfLibaray+1) + actualRoadBuild * self.costRoad
        totalCostOfLibaray = self.calculateCostofLibrary(self.numberCity)
        print(min(totalCostOfroad,totalCostOfLibaray))


q = int(input().strip())
for a0 in range(q):
    n, m, x, y = input().strip().split(' ')
    n, m, x, y = [int(n), int(m), int(x), int(y)]
    city = City(n, m, x, y)
    for a1 in range(m):
        city_1, city_2 = input().strip().split(' ')
        city_1, city_2 = [int(city_1), int(city_2)]
        city.addEdge(city_1,city_2)
    city.totalCost()


<file_sep>class Heap(object):

    HEAP_SIZE = 10

    def __init__(self):
        self.heap = [0] * Heap.HEAP_SIZE
        self.currentPosition = -1

    def insert(self, item):
        if self.isFull():
            return
        self.currentPosition += 1
        self.heap[self.currentPosition] = item
        self.fixUp(self.currentPosition)

    def isFull(self):
        return self.currentPosition == Heap.HEAP_SIZE

    def fixUp(self, index):
        parentIndex = (index-1) //2

        while parentIndex >= 0 and self.heap[parentIndex] < self.heap[index]:
            (self.heap[parentIndex],self.heap[index]) = (self.heap[index],self.heap[parentIndex])
            parentIndex = (index - 1) // 2

    def heapSort(self):
        for i in range(0,self.currentPosition+1):
            temp = self.heap[0]
            self.heap[0] = self.heap[self.currentPosition-i]
            self.heap[self.currentPosition-i] = temp
            self.fixDown(0, self.currentPosition-i-1)

    def fixDown(self, index, upto):
        while index <= upto:
            leftChild = 2 * index + 1
            rightChild = 2 * index + 2

            if leftChild < upto:
                swapChild = None

                if rightChild > upto:
                    swapChild = leftChild
                else:
                    if self.heap[leftChild] > self.heap[rightChild]:
                        swapChild = leftChild
                    else:
                        swapChild = rightChild

                if self.heap[index] < self.heap[swapChild]:
                    temp = self.heap[index]
                    self.heap[index] = self.heap[swapChild]
                    self.heap[swapChild] = temp
                else:
                    break
                index = swapChild
            else:
                break

heap = Heap()
heap.insert(10)
heap.insert(-20)
heap.insert(0)
heap.insert(2)
heap.heapSort()
print(heap.heap)



<file_sep>class AVLNode(object):

    def __init__(self,data):
        self.data = data
        self.right = None
        self.left = None
        self.height = 0

class AVLTree(object):

    def __init__(self):
        self.root = None

    def calHeight(self, root):
        if root is None:
            return -1
        return root.height

    def calcBalance(self, root):
        if root is None:
            return 0
        return self.calHeight(root.left) - self.calHeight(root.right)

    def rightRotation(self, root):
        print("Rotating to the right " + str(root.data))
        templeft = root.left
        t = templeft.right
        templeft.right = root
        root.left = t
        root.height = max(self.calHeight(root.left), self.calHeight(root.left)) +1
        templeft.height = max(self.calHeight(templeft.left), self.calHeight(templeft.left)) +1
        return templeft

    def leftRotation(self, root):
        print("Rotating to the left " + str(root.data))
        tempright = root.right
        t = tempright.left
        tempright.left = root
        root.right = t
        root.height = max(self.calHeight(root.left), self.calHeight(root.left)) +1
        tempright.height = max(self.calHeight(tempright.left), self.calHeight(tempright.left)) +1
        return tempright

    def insert(self, data):
        self.root = self.insertNode(self.root, data)

    def insertNode(self,root, data):
        if root is None:
            return AVLNode(data)
        if data <= root.data:
            root.left = self.insertNode(root.left, data)
        elif data > root.data:
            root.right = self.insertNode(root.right, data)

        root.height = max(self.calHeight(root.left), self.calHeight(root.right)) + 1

        return self.settleBalance(root, data)

    def settleBalance(self, root, data):
        balance = self.calcBalance(root)
        #Case 1 tree is heavily left unbalanced
        if balance > 1 and data < root.left.data:
           return self.rightRotation(root)

        if balance < -1 and data > root.right.data:
            return self.leftRotation(root)

        if balance > 1 and data > root.left.data:
            root.left = self.leftRotation(root.left)
            return self.rightRotation(root)

        if balance < -1 and data < root.right.data:
            root.right = self.rightRotation(root.right)
            return self.leftRotation(root)

        return root


    def inOrder(self, root):
        if root is None:
            return
        else:
            self.inOrder(root.left)
            print(root.data)
            self.inOrder(root.right)

tree = AVLTree()
tree.insert(21)
tree.insert(26)
tree.insert(30)
tree.insert(9)
tree.insert(4)
tree.insert(14)
tree.insert(28)
tree.insert(18)
tree.insert(15)
tree.insert(10)
tree.insert(2)
tree.insert(3)
tree.insert(7)
tree.inOrder(tree.root)<file_sep>class Node(object):

    def __init__(self,data):
        self.data = data
        self.parent = None
        self.rank = 0

class DisjointSet(object):
    listOfSet = {}

    def makeSet(self, data):
        new_node = Node(data)
        new_node.parent = new_node
        self.listOfSet[data] = new_node

    def union(self,data1, data2):

        node1 = self.listOfSet[data1]
        node2 = self.listOfSet[data2]

        parent1 = self.findSet(node1)
        parent2 = self.findSet(node2)

        if parent1.data == parent2.data:
            return
        if parent1.rank >= parent2.rank:
            parent1.rank = parent1.rank + 1 if parent1.rank == parent2.rank else parent1.rank
            #parent1.rank = parent1.rank  + 1
            parent2.parent = parent1
        else:
            parent2.rank = parent2.rank + 1
            parent1.parent = parent2

    def findSetByCompersion(self,node):
        if node.parent == node:
            return node
        node.parent = self.findSet(node.parent)
        return  node.parent

    def findSetData(self,data):
        return self.findSet(self.listOfSet[data]).data
        #return self.findSet(self.listOfSet[data]).rank

class Graph(object):

    def __init__(self):
        self.edges = []
        self.vertex = []
        self.ds = DisjointSet()

    def hasCycle(self):

        for i in self.getAllVertex():
            self.ds.makeSet(i)

    def getAllVertex(self):
        return self.vertex




<file_sep>class Queue(object):

    def __init__(self):
        self.queue = []
        self.top = None
        self.end = None

    def enqueue(self,data):
        self.queue.append(data)
        self.top = self.queue[0]
        if self.end is None:
            self.end = self.queue[-1]

    def dequeue(self):
        try:
            res = self.queue.pop(0)
            self.top = self.queue[0]
        except IndexError:
            self.top = None
            self.end = None

    def getTop(self):
        return self.top

    def display(self):
        print(' '.join(list(map(str,self.queue))))

q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(4)
q.enqueue(7)
q.display()
q.dequeue()
q.display()
print(q.getTop())<file_sep>class Stack(object):

    def __init__(self, limit=10):
        self.stk = []
        self.top = None
        self.limit = limit

    def push(self,data):
        if len(self.stk) == self.limit:
            print('Stack Overflow')
            return
        self.stk.append(data)

    def length(self):
        return len(self.stk)

    def pop(self):
        if self.isEmpty():
            print('Stack is Underflow')
            return
        return self.stk.pop()

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

    def display(self):
        if self.isEmpty():
            print('Stack is Empty')
            return
        print(' '.join(list(map(str,self.stk))))

    def getTop(self):
        try:
            return self.stk[-1]
        except IndexError:
            print('Stack is Empty')

stk = Stack()
stk.push(3)
stk.push(4)
print(stk.getTop())
stk.pop()
stk.push(9)
stk.push(10)
stk.pop()
stk.display()
print(stk.getTop())
<file_sep>n = int(input())
def numFriendsGreeted(a,b,max):
    count = 0
    for i in range(a,max+1,b):
        count += 1
    return count
for _ in range(n):
    user_input = list(map(int, input().split()))
    print(user_input)
    print(numFriendsGreeted(user_input[0],user_input[1],user_input[2]))

<file_sep>import heapq
INF = 100000
class PriorityQueueMap(object):
    def __init__(self):
        self.eq = []
        self.entry_finder = {}

    def add(self, key, prioprity=INF):
        if key in self.entry_finder:
            raise KeyError("Key already exists")
        self.entry_finder[key] = prioprity
        heapq.heappush(self.eq, [prioprity, key])

    def delete(self, task):
        if not task in self.entry_finder:
            raise KeyError("Key doesnt exist")
        self.entry_finder.pop(task)

    def getMin(self):
        minVertex = heapq.heappop(self.eq)[1]
        self.entry_finder.pop(minVertex)
        return minVertex

    def descrease(self, key, priority):
        previousPriority = self.entry_finder[key]
        self.entry_finder[key] = priority
        index = self.eq.index([previousPriority, key])
        del self.eq[index]
        heapq.heappush(self.eq, [priority, key])


