import java.util.LinkedList;
 import java.util.List;
 import java.util.Queue;
 import java.util.Scanner;
 import java.util.Stack; 

public class Graph {

 private int numV; // # of vertices
   private boolean isdirected; // is it a directed graph?
   private List<Edge>[] edges;

 public Graph(int numV, boolean isdirected) {
   this.numV = numV;
   this.isdirected = isdirected;

 edges = new List[numV];
   for (int i = 0; i < numV; i++) {
   edges[i] = new LinkedList<Edge>();
   }
   }

 public int getNumV() { // Returns the # of vertices
   return numV;
   }

 public boolean isDirected() { // Is this a directed graph?
   return isdirected;
   }
   
   public boolean isEmpty() {
   return numV == 0;
   }
   
   public void clear() {
   numV = 0;
   isdirected = false;
   edges = null;
   }

 void insert(Edge edge) { // Insert a new edge into the graph
   edges[edge.getSource()].add(edge);
   if (!isDirected()) {
   edges[edge.getDest()].add(new Edge(edge.getDest(),
   edge.getSource(), edge.getWeight()));
   }
   }

 boolean isEdge(int source, int dest) { // Is there an edge <source, dest>?
   return edges[source].contains(new Edge(source, dest));
   }

 public void dfTraversal() {
   boolean[] visited = new boolean[numV];
   for (int i = 0; i < visited.length; i++) {
   visited[i] = false;
   }

 for (int i = 0; i < numV; i++) {
   if (!visited[i])
   dft(i, visited);
   }
   }

 private void dft(int v, boolean[] visited) {

 System.out.println(v); // visit the node
   visited[v] = true;

 for (Edge e : edges[v]) {
   int w = e.getDest();
   if (!visited[w])
   dft(w, visited);
   }
   }
   
   public void depthFirst() {
   Stack<Integer> queue = new Stack<Integer>();
   boolean[] visited = new boolean[numV];
   for (int i = 0; i < visited.length; i++)
   visited[i] = false;

 for (int i = 0; i < numV; i++) {
   if (!visited[i]) {
   queue.push(i);

 while (!queue.isEmpty()) {
   int u = queue.pop();
   visited[u] = true;
   System.out.println(u);
   for (Edge e : edges[u]) {
   int w = e.getDest();
   if (!visited[w]) {
   queue.push(w);
   }
   }
   }

 }
   }
   }
   
   public void bfTraversal() {
   Queue<Integer> queue = new LinkedList<Integer>();
   boolean[] visited = new boolean[numV];
   for (int i = 0; i < visited.length; i++)
   visited[i] = false;

 for (int i = 0; i < numV; i++) {
   if (!visited[i]) {
   queue.add(i);
   visited[i] = true;
   System.out.println(i);
   }
   while (!queue.isEmpty()) {
   int u = queue.remove();
   for (Edge e : edges[u]) {
   int w = e.getDest();
   if (!visited[w]) {
   queue.add(w);
   visited[w] = true;
   System.out.println(w);
   }
   }
   }
   }
   }

 public void readGraph(Scanner scan) {
   String line;
   while (scan.hasNextLine()) {
   line = scan.nextLine();
   String[] tokens = line.split("\\s+");
   int source = Integer.parseInt(tokens[0]);
   int dest = Integer.parseInt(tokens[1]);
   double weight = 1.0;
   if (tokens.length == 3) {
   weight = Double.parseDouble(tokens[2]);
   }
   insert(new Edge(source, dest, weight));
   }
   }

 public String toString() {
   // print out the vertices
   String G = (isdirected ? "Directed ": "Undirected ") + "Graph:\nVertices: <";
   for (int i = 0; i < edges.length - 1; i++) {
   G += i + ", ";
   }
   G += edges.length - 1 + ">\n";
   // print out the edges
   G += "Edges:\n";
   for (int i = 0; i < numV; i++) {
   for (int j = 0; j < edges[i].size(); j++) {
   G += edges[i].get(j) + "\n";
   }
   }
   return G;
   }
   }