import java.util.*;
/** 4. Hozzuk létre a Graph másik leszármazottját, a SparseGraph-ot, amely a ritka gráfok tárolására optimális. Az éleket tároljuk egy gyorsan indexelheto ArrayList-ben, ennek minden eleme egy Set, amiben benne vannak azok a csúcsok amelyek az adott sorszámú csúcsból elérhetok. Implementáljuk le a hasEdge, edgesFrom és addEdge függvényeket ennek megfeleloen. */
class SparseGraph extends Graph{	
	ArrayList<Edge> edges;
	
	public SparseGraph(int size){
		edges=new ArrayList<Edge>(size);
		//edges=new ArrayList<TreeSet<Integer> >...
	}

	public boolean hasEdge(int i, int j){
		for(Edge e : edges){
			if(e.i==i && e.j==j){
				return true;
			}
		}
		return false;
	}

	Set<Integer> edgesFrom(int i){
		//3ICE: Ha ArrayList of TreeSet adatstruktúrával dolgooztam volna, ahogy a feladat kéri, akkor egysoros lenne ez a metódus:
		//return edges.get(i);
		//3ICE: De én helyette egy extra "Edge" osztályt használtam
		//3ICE: Cserébe az addEdge metódusom egysoros :)
		TreeSet<Integer> ret=new TreeSet<>();
		for(Edge e : edges){
			if(e.i==i){
				ret.add(e.j);
			}
		}
		return ret;
	}

	void addEdge(int i, int j){
		edges.add(new Edge(i, j));
		//3ICE: Alternatív megoldás (ArrayList of TreeSet esetén)
		//edges.get(i).add(j)
	}

}