class Graph:
    #Constructor, Time O(1) Space O(1)
    def __init__(self, directed):
        self.adj = {}
        self.directed = directed #true or false 
	
	#Add edges including adding nodes, Time O(1) Space O(1)
    def addEdge(self, a, b):    
        if a not in self.adj:
            self.adj[a] = []
        if b not in self.adj:
            self.adj[b] = []   		
        self.adj[a].append(b)
        if (self.directed == False):
            self.adj[b].append(a)		
	
	#Remove direct connection between a and b, Time O(1) Space O(1)
    def removeEdge(self, a, b):
        if a not in self.adj or b not in self.adj:
            return False
        ne1 = self.adj[a]
        ne2 = self.adj[b] 
        if ne1 == None or ne2 == None:
            return False
        if b not in ne1:
            return False
        ne1.remove(b)
        if (self.directed == False):
            if a not in ne2:
                return False
            ne2.remove(a)
        return True
        
    #Remove a node including all its edges, 
	#Time O(V+E) Space O(1), 
    def removeNode(self, a): 
        if a not in self.adj:
            return False      
        if self.directed == False:  #undirected
            ne1 = self.adj[a]
            for node in ne1: 
                self.adj[node].remove(a)
        else: #directed
            for k, v in self.adj.items(): 
                if a in v:
                    v.remove(a)	
        self.adj.pop(a)
        return True
			
	#Check whether there is node by its key, Time O(1) Space O(1)
    def hasNode(self, key):
        return key in self.adj.keys()
	
	#Check whether there is direct connection between two nodes, Time O(1), Space O(1)
    def hasEdge(self, a, b):
        if a not in self.adj or b not in self.adj:
            return False
        ne1 = []
        ne2 = []
        if a in self.adj:
            ne1 = self.adj[a]
        if self.directed: #directed
            return b in ne1
        else: #undirected or bi-directed
            if b in self.adj:
                ne2 = self.adj[b]
            return b in ne1 and a in ne2
		
    # Check there is path from src and dest
	# DFS, Time O(V+E), Space O(V)
    def dfs(self, src, dest): 
        if src not in self.adj or dest not in self.adj:
            return False
        visited = {}
        return self.dfsHelper(src, dest, visited)
	
	#DFS helper, Time O(V+E), Space O(V) 
    def dfsHelper(self, v, dest, visited):
        if v == dest:
            return True
        visited[v] = True
        for ne in self.adj[v]:
            if ne not in visited:
                return self.dfsHelper(ne, dest, visited)
        return False

	#Check there is path from src and dest
	#BFS, Time O(V+E), Space O(V)
    def bfs(self, src, dest): 
        if src not in self.adj or dest not in self.adj:
            return False
        visited = {} 
        q = [] 
        visited[src] = True
        q.append(src) 
        while q: 
            v = q.pop(0)
            for ne in self.adj[v]:
                if ne == dest: 
                    return True 
                if ne not in  visited:  
                    q.append(ne)
                    visited[ne] = True	    	        
        return False 

	# Print graph as hashmap, Time O(V+E), Space O(1)
    def printGraph(self):
        for k, v in self.adj.items():
            print(str(k) + "-" + str(v))
		
	#Traversal starting from src, DFS, Time O(V+E), Space O(V)
    def dfsTraversal(self, src):
        if src not in self.adj:
            return 
        visited = {}
        self.helper(src, visited)
	
	#DFS helper, Time O(V+E), Space O(V) 
    def helper(self, v, visited):
        visited[v] = True
        print(str(v))
        for ne in self.adj[v]:
            if ne not in visited:
                self.helper(ne, visited)
    
    # Traversal starting from src, BFS, Time O(V+E), Space O(V)
    def bfsTraversal(self, src): 
        if src not in self.adj:
            return
        q = [] 
        visited = {} 
        q.append(src) 
        visited[src] = True 
        while (len(q) > 0): 
            v = q.pop(0) 
            print(str(v) + " ")    
            for  ne in self.adj[v]:   
                if ne not in visited:
                    q.append(ne) 
                    visited[ne] = True
	 
if __name__ == "__main__":
    #  Test case 1, Undirected graph
    #     1-- 3
    #     | / |
    #     2   4  
    g = Graph(False)
    g.addEdge(1, 3)
    g.addEdge(1, 2)
    g.addEdge(2, 3)
    g.addEdge(3, 4)
    print("Undirected graph: ")
    g.printGraph()  
    start = 1
    print("DFS: ")
    g.dfsTraversal(start) 
    print("BFS: ")
    g.bfsTraversal(start)

    #Has node
    k = 4
    print("Has node " + str(k) + ": " + str(g.hasNode(k)))

    #has edge
    a = 2
    b = 4
    print("Has edge from " + str(a) + " to " + str(b) + ": " + str(g.hasEdge(a, b)))

    #has path
    print("Has path from " + str(a) + " to " + str(b) + " (dfs): " + str(g.dfs(a, b)))
    print("Has path from " + str(a) + " to " + str(b) + " (bfs): " + str(g.bfs(a, b)))

    #remove edge
    c = 2
    d = 3
    print("After remove edge (" + str(c) + "," + str(d) + ")")
    g.removeEdge(c, d)
    g.printGraph()
    g.addEdge(c, d) #add back

    #remove node
    n = 2
    print("After remove node " + str(n))
    g.removeNode(n)
    g.printGraph()
    print()

    # Test case 2, Directed graph
    # 1-->2
    # |   |
    # V   V
    # 3-->4
    #     |
    #     V
    # 5<--6        

    g1 = Graph(True)
    g1.addEdge(1, 2)
    g1.addEdge(1, 3)
    g1.addEdge(2, 4)
    g1.addEdge(3, 4)
    g1.addEdge(4, 6)
    g1.addEdge(6, 5)
    print("Directed graph:") 
    g1.printGraph()  
    print("DFS: ")
    g1.dfsTraversal(start) 
    print("BFS: ")
    g1.bfsTraversal(start)

    #Has node
    k = 5
    print("Has node " + str(k) + ": " + str(g1.hasNode(k)))

    #has edge
    a = 2
    b = 5
    print("Has edge from " + str(a) + " to " + str(b) + ": " + str(g1.hasEdge(a, b)))

    #has path
    print("Has path from " + str(a) + " to " + str(b) + " (dfs): " + str(g1.dfs(a, b)))
    print("Has path from " + str(a) + " to " + str(b) + " (bfs): " + str(g1.bfs(a, b)))

    c = 2
    d = 4
    print("After remove edge (" + str(c) + "," + str(d) + ")")
    g1.removeEdge(c, d)
    g1.printGraph()
    g1.addEdge(c, d) #add back

    #remove node
    n = 3
    print("After remove node " + str(n))
    g1.removeNode(n)
    g1.printGraph()