import java.util.*;

public class Graph 
{
	protected ArrayList<String> vertex;
	protected HashMap<String, ArrayList<ArrayList<String>>> edge;
	
	/*The constructor*/
	public Graph()
	{
		vertex = new ArrayList<String>();
		edge = new HashMap<String, ArrayList<ArrayList<String>>>();
	}
	
	/*This method is used to input a new vertex.*/
	public void insertVertex(String v)
	{
		vertex.add(v);
		edge.put(v, new ArrayList<ArrayList<String>>());
	}
	
	/*This method is used to insert a new edge*/
	public void insertEdge(String s, String d, String w)
	{
		if (! (vertex.contains(s) && vertex.contains(d)))
		{
			System.out.println("At least one of the vertices you input does not exist!");
			return;
		}
		
		ArrayList<String> l = new ArrayList<String>();
		l.add(d);
		l.add(w);

		ArrayList<ArrayList<String>> temp = edge.get(s);
		temp.add(l);
	}
	
	/*This method is used to remove a vertex.*/
	public void removeVertex(String v)
	{
		if (! vertex.contains(v))
		{
			System.out.println("The vertex you input does not exist in the graph!");
			return;
		}

		vertex.remove(v);
		edge.remove(v);
		
		for (String s : vertex)
		{
			ArrayList<ArrayList<String>> a = edge.get(s);
			for (ArrayList<String> b : a)
				if (b.contains(v))
					a.remove(b);
		}
	}

	/*This method is used to remove an edge*/
	public void removeEdge(String s, String d)
	{
		if (! (vertex.contains(s) && vertex.contains(d)))
			return;

		ArrayList<ArrayList<String>> a = edge.get(s);
		for (ArrayList<String> b : a)
			if (b.get(0).equals(d))
			{
				a.remove(b);
				break;
			}
	}

	/*This method is used to replace an existing vertex with the input vertex.*/
	public void replaceVertex(String o, String n)
	{
		if (! vertex.contains(o))
		{
			System.out.println("The origin vertex you want to replace with does not exist!");
			return;
		}
		else if (vertex.contains(n))
		{
			System.out.println("The new vertex you want to replace with exists already!");
			return;
		}
		
		vertex.set(vertex.indexOf(o), n);

		ArrayList<ArrayList<String>> l = edge.get(o);
		edge.remove(o);
		edge.put(n, l);

		for (String v : vertex)
		{
			ArrayList<ArrayList<String>> a = edge.get(v);
			for (ArrayList<String> b : a)
				if (b.contains(o))
					b.set(b.indexOf(o), n);
		}
	}

	/*This method is used to check whether the two inputed vertices are adjacency or not.*/
	public boolean areAdjacent(String s, String d)
	{
		if (! (vertex.contains(s) && vertex.contains(d)))
		{
			System.out.println("At least one of the vertices you input does not exist!");
			return false;
		}

		ArrayList<ArrayList<String>> a = edge.get(s);
		for (ArrayList<String> b : a)
			if (b.get(0).equals(d))
				return true;
		return false;
	}
}