public class Graph {
    private Vertex [] vertices;
    private boolean directed; // true if the graph is directed

    public Graph(int n, boolean directed) {
	vertices = new Vertex [n];
	this.directed = directed;
	for (int i = 0; i < n; ++i) {
	    vertices[i] = new Vertex(i);
	}
    }

    public void setEdges(int [] startPoints, int [] endPoints) {
	if (startPoints.length != endPoints.length) {
	    throw new RuntimeException ("Invalid edges data");
	}
	if (directed) {
	    for (int i = 0 ; i < startPoints.length; ++i) {
		vertices[startPoints[i]].addEdge(vertices[endPoints[i]]);
	    }
	} else {
	    // need to set both directions
	    for (int i = 0 ; i < startPoints.length; ++i) {
		vertices[startPoints[i]].addEdge(vertices[endPoints[i]]);
		vertices[endPoints[i]].addEdge(vertices[startPoints[i]]);
	    }
	}
    }

    public String toString() {
	String toPrint = "";
	for (int i = 0; i < vertices.length; ++i) {
	    toPrint += "vertex " + vertices[i].getId();
	    toPrint += " Connected to:"; 
	    VertexNode current = vertices[i].getEdges();
	    while (current != null) {
		toPrint += " " +  current.getLink().getId();
		current = current.getNext();
	    }
	    toPrint += "\n";
	}
	return toPrint;
    }
    
    public void BFT() {
	// the array holds distances from the starting vertex
	int [] distances = new int [vertices.length];
	// -1 stands for infinity
	for (int i = 0; i < distances.length; ++i ) {
	    distances[i] = -1;
	}
	IntQueue queue = new IntQueue();
	
	queue.enqueue(0);
	distances[0]=0;
	
	while(!queue.isEmpty()){
	    int n=queue.dequeue();
	    VertexNode v = vertices[n].getEdges();
	    while (v != null) {
		int x = v.getLink().getId();
		if(distances[x] == -1) {
		    queue.enqueue(x);
		    distances[x] = distances[n]+1;
		}
		v = v.getNext();
		
	    }
	}
	
	// print out the distances from vertex 0 to each vertex
	for (int i = 0; i < distances.length; ++i) {
	    System.out.println("vertex: " + i + " distance: " + distances[i]);
	}
    }

    public void DFT() {
	// the array holds distances from the starting vertex
	int [] distances = new int [vertices.length];
	// -1 stands for infinity
	for (int i = 0; i < distances.length; ++i ) {
	    distances[i] = -1;
	}
	IntStack stack = new IntStack();
	
	stack.push(0);
	distances[0]=0;
	
	while(!stack.isEmpty()){
	    int n = stack.pop();
	    VertexNode v = vertices[n].getEdges();
	    while (v != null) {
		int x = v.getLink().getId();
		if(distances[x] == -1) {
		    stack.push(x);
		    distances[x] = distances[n]+1;
		}
		v = v.getNext();
		
	    }
	}
	
	// print out the distances from vertex 0 to each vertex
	for (int i = 0; i < distances.length; ++i) {
	    System.out.println("vertex: " + i + " distance: " + distances[i]);
	}
    }
}

public class VertexNode {
    private Vertex linkTo;
    private VertexNode next;

    public VertexNode(Vertex linkTo, VertexNode next) {
	this.linkTo = linkTo;
	this.next = next;
    }

    public Vertex search(Vertex v) {
	VertexNode current = this;
	while (current != null) {
	    if (current.linkTo.equals(v)) {
		return v;
	    }
	}
	return null;
    }

    public Vertex getLink() {
	return linkTo;
    }
    
    public VertexNode getNext() {
	return next;
    }
}

public class Vertex {
    private int id;
    private VertexNode edges;

    public Vertex(int id) {
	this.id = id;
    }

    public void addEdge(Vertex v) {
	VertexNode vn = new VertexNode(v,edges);
	edges = vn;
    }

    public boolean equals(Object o) {
	Vertex v = (Vertex) o;
	if (v.id == this.id) {
	        return true;
	}
	return false;
    }

    public int getId() {
	return id;
    }

    public VertexNode getEdges() {
	return edges;
    }
}

public class TestGraphs {
    public static void main(String [] args) {
	Graph g = new Graph(10,false); // undirected graph
	int [] starts = {0, 6, 3, 4, 2, 3, 5, 7, 8, 0, 9, 1};
	int [] ends = {1, 2, 0, 7, 3, 1, 2, 5, 6, 8, 4, 9};
	g.setEdges(starts, ends);
	//System.out.println(g);
	System.out.println("BFT:");
	g.BFT();
	System.out.println("DFT:");
	g.DFT();
    }
}