import java.util.Set;
import java.util.HashSet;
import java.util.ArrayList;

class SparseGraph <E extends Edge> extends Graph<E> {
	ArrayList<HashSet<E>> edges = new ArrayList<>();
	
	public SparseGraph(int n) {
		for (int i = 0; i < n; ++i) {
			edges.add(new HashSet<E>());
		}
	}
	
	boolean hasEdge(int i, int j) {
		for(E e : edges.get(i)){
			if(e.getTarget()==j) return true;
		}
		return false;
	}
	
	Set<E> edgesFrom(int i) {
		return new HashSet(edges.get(i));
	}
	
	void addEdge(E e) {
		edges.get(e.getSource()).add(e);
	}
}