import java.util.*;

class Edge<T> { 
	T neighbor; //connected vertex
	int weight; //weight
	
	//Constructor, Time O(1) Space O(1)
	public Edge(T v, int w) {
		this.neighbor = v; 
		this.weight = w;
	}
	
	//Time O(1) Space O(1)
	@Override
	public String toString() {
		return "(" + neighbor + "," + weight + ")";
	}
}

public class WeightedGraph<T> {
	Map<T, LinkedList<Edge<T>>> adj = new HashMap<>() ;
	boolean directed;
	
	//Constructor, Time O(1) Space O(1)
	public WeightedGraph () {
		directed = false; //default, Undirected graph
	}
	
	//Constructor, Time O(1) Space O(1)
	public WeightedGraph(boolean d) {
		directed = d;
	}
	
	//Add edges including adding nodes, Time O(1) Space O(1)
	public void addEdge(T a, T b, int w) {
		adj.putIfAbsent(a, new LinkedList<>()); //add node
		adj.putIfAbsent(b, new LinkedList<>()); //add node
		Edge<T> edge1 = new Edge<>(b, w);
		adj.get(a).add(edge1); //add edge
		if (!directed) { //undirected
			Edge<T> edge2 = new Edge<>(a, w);
			adj.get(b).add(edge2);
		}			
	}
	
	//Find the edge between two nodes, Time O(n) Space O(1), n is number of neighbors 
	private Edge<T> findEdgeByNodes(T a, T b) {
		if (!adj.containsKey(a) || !adj.containsKey(b)) //invalid input
			return null;
		LinkedList<Edge<T>> ne = adj.get(a);
		for (Edge<T> edge: ne) {
			if (edge.neighbor.equals(b)) {
				return edge;
			}
		}
		return null;
	}
	
	//Remove direct connection between a and b, Time O(n) Space O(1)
	public boolean removeEdge(T a, T b) {
		if (!adj.containsKey(a) || !adj.containsKey(b)) //invalid input
			return false;
		LinkedList<Edge<T>> ne1 = adj.get(a);
		LinkedList<Edge<T>> ne2 = adj.get(b); 
		if (ne1 == null || ne2 == null)
			return false;
		Edge<T> edge1 = findEdgeByNodes(a, b);
		if (edge1 == null)
			return false;
		ne1.remove(edge1);
		if (!directed) {//undirected
			Edge<T> edge2 = findEdgeByNodes(b, a);
			if (edge2 == null)
				return false;
			ne2.remove(edge2);
		}
		return true;
	}
	
	//Remove a node including all its edges, Time O(V+E) Space O(1), 
	//V is number of nodes, E is number of edges
	public boolean removeNode(T a) {	
		if (!adj.containsKey(a)) //invalid input
			return false;	
		if (!directed) { //undirected
			LinkedList<Edge<T>> ne1 = adj.get(a);
			for (Edge<T> edge: ne1) {	
				Edge<T> edge1 = findEdgeByNodes(edge.neighbor, a);
				adj.get(edge.neighbor).remove(edge1);
			}
		} else { //directed
			for (T key: adj.keySet()) {
				Edge<T> edge2 = findEdgeByNodes(key, a);
				if (edge2 != null)
					adj.get(key).remove(edge2);
			}
		}
		adj.remove(a);
		return true;
	}
	
	//Check whether there is node by its key, Time O(1) Space O(1)
	public boolean hasNode(T key) {
		return adj.containsKey(key);
	}
	
	//Check whether there is direct connection between two nodes, Time O(n), Space O(1)
	public boolean hasEdge(T a, T b) {
		Edge<T> edge1 = findEdgeByNodes(a, b);
		if (directed) {//directed
			return edge1 != null;
		}
		else { //undirected or bi-directed
			Edge<T> edge2 = findEdgeByNodes(b, a);
			return edge1 != null && edge2!= null;
		}
	}
	
	//Check if there is path from src and dest
	//DFS, Time O(V+E), Space O(V)
	public boolean dfsHasPath(T src, T dest) {
		if (!adj.containsKey(src) || !adj.containsKey(dest)) //invalid input
			return false;
		HashMap<T, Boolean> visited = new HashMap<>();
	    return dfsHelper(src, dest, visited);
	}
	
	//DFS helper, Time O(V+E), Space O(V) 
	private boolean dfsHelper(T v, T dest, HashMap<T, Boolean> visited) {
		if (v == dest)
			return true;
	    visited.put(v, true);
	    for (Edge<T> edge : adj.get(v)) {
	    	T u = edge.neighbor;
	        if (visited.get(u) == null)
	            return dfsHelper(u, dest, visited);
	    }
	    return false;
	}
	
	//Check if there is path from src and dest
	//BFS, Time O(V+E), Space O(V), V is number of vertices, E is number of edges
	public boolean bfsHasPath(T src, T dest) {
		if (!adj.containsKey(src) || !adj.containsKey(dest)) //invalid input
			return false;
		HashMap<T, Boolean> visited = new HashMap<>(); 
		Queue<T> q = new LinkedList<>();
		visited.put(src, true);
        q.offer(src);
        while (!q.isEmpty()) {
            T v = q.poll();
            if (v == dest) {
                return true;
            }
            for (Edge<T> edge: adj.get(v)) {
	           T u = edge.neighbor;		           
	           if (visited.get(u) == null) {
	        	   visited.put(u, true);
                   q.offer(u);
               }	            
           }
        }     
        return false;
	}
	
	//Print graph as hashmap, Time O(V+E), Space O(1)
	public void printGraph() {
		for (T key: adj.keySet()) {
			System.out.println(key + "," + adj.get(key));
		}	
	}
	
	//Traversal starting from src, DFS, Time O(V+E), Space O(V)
	public void dfsTraversal(T src) {
		if (!adj.containsKey(src)) //invalid input
			return;
		HashMap<T, Boolean> visited = new HashMap<>();
	    helper(src, visited);
	    System.out.println();
	}
	
	//DFS helper, Time O(V+E), Space O(V) 
	private void helper(T v, HashMap<T, Boolean> visited) {
	    visited.put(v, true);
	    System.out.print(v.toString() + " ");
	    for (Edge<T> edge : adj.get(v)) {
	    	T u = edge.neighbor;
	        if (visited.get(u) == null)
	            helper(u, visited);
	    }
	}
	
	//Traversal starting from src, BFS, Time O(V+E), Space O(V)
	public void bfsTraversal(T src) { 
		if (!adj.containsKey(src)) //invalid input
			return;
	    Queue<T> q = new LinkedList<>(); 
	    HashMap<T, Boolean> visited = new HashMap<>(); 
	    q.add(src); 
	    visited.put(src, true); 
	    while (!q.isEmpty()) { 
	        T v = q.poll(); 
	        System.out.print(v.toString() + " ");        
	        for (Edge<T> edge : adj.get(v)) { 
	        	T u = edge.neighbor;
	            if (visited.get(u) == null) { 
	                q.add(u); 
	                visited.put(u, true); 
	            } 
	        }   
	    } 
	    System.out.println(); 
	} 
	
	public static void main(String[] args) {
		/*
		 Test case 1, Undirected graph
		 1-- 3
		 | \ |
		 2   4 
		*/
		WeightedGraph<Integer> g = new WeightedGraph<>(); 
		g.addEdge(1, 2, 26); 
		g.addEdge(1, 3, 13);  
		g.addEdge(1, 4, 28);   
		g.addEdge(3, 4, 19);
		System.out.println("undirected graph:");
		g.printGraph();
		System.out.println("dfs:");
		g.dfsTraversal(1);
		System.out.println("bfs:");
		g.bfsTraversal(1);
		
		g.removeEdge(3, 4);
		System.out.println("after remove edge:");
		g.printGraph();
		g.addEdge(3, 4, 20); //add back
		
		System.out.println("has node 3:"+ g.hasNode(3));
		System.out.println("has node 5:"+ g.hasNode(5));
		System.out.println("has edge 3,2: "+ g.hasEdge(3,2));
		System.out.println("has edge 3,1: "+ g.hasEdge(3,1));		
		System.out.println("has path 2,3 (DFS): " + g.dfsHasPath(2, 3));
		System.out.println("has path 2,5 (DFS): " + g.dfsHasPath(2, 5));
		System.out.println("has path 2,3 (BFS): " + g.bfsHasPath(2, 3));
		System.out.println("has path 2,5 (BFS): " + g.bfsHasPath(2, 5));
		
		g.removeNode(1);
		System.out.println("after remove node:");
		g.printGraph();
		System.out.println();
				
		/*
		 * directed graph
		 * 2\      / 5 <
		 *   >   <   ^  \
		 *    1 <    |   6
		 *   >    <  |  /
		 * 4 / <-- \ 3<
		 */
		WeightedGraph<Integer> g1=new WeightedGraph<>(true); 
		g1.addEdge(6, 5, 26); 
		g1.addEdge(6, 3, 13);  
		g1.addEdge(3, 5, 28);   
		g1.addEdge(5, 1, 19);
		g1.addEdge(3, 1, 35);  
		g1.addEdge(3, 4, 27);  
		g1.addEdge(4, 1, 11);  
		g1.addEdge(2, 1, 38);  
		System.out.println("directed graph:");
		g1.printGraph();
		System.out.println("dfs:");
		g1.dfsTraversal(3);
		System.out.println("bfs:");
		g1.bfsTraversal(3);
		
		System.out.println("has node 3:" + g1.hasNode(3));
		System.out.println("has node 5:" + g1.hasNode(5));
		System.out.println("has edge 6,5: "+ g1.hasEdge(6,5));
		System.out.println("has edge 4,2: "+ g1.hasEdge(4,2));
		System.out.println("has path 6,1 (DFS): " + g1.dfsHasPath(6, 1));
		System.out.println("has path 2,3 (DFS): " + g1.dfsHasPath(2, 3));
		System.out.println("has path 6,1 (BFS): " + g1.bfsHasPath(6, 1));
		System.out.println("has path 2,3 (BFS): " + g1.bfsHasPath(2, 3));
		
		g1.removeEdge(6, 5);
		System.out.println("after remove edge:");
		g1.printGraph();
		g.addEdge(6, 5, 3); //add back
		
		g1.removeNode(5);
		System.out.println("after remove node:");
		g1.printGraph();
	}
}