import java.io.*;
import java.util.Scanner;
import java.util.Vector;
import java.util.Deque;
import java.util.ArrayDeque;

public class UndirectedConnectivity {

  public static void errPrint(String s) {
    System.err.print(s);
  }

  public static void errPrintln(String s) {
    System.err.println(s);
  }

  public static void depthFirstSearch(int u, boolean[] visited, Graph graph) {
    if (visited[u]) return;
    visited[u] = true;
    for (Integer v : graph.edges.get(u)) {
      depthFirstSearch(v, visited, graph);
    }
  }

  public static void dfsNonrecursive(int s, boolean[] visited, Graph graph) {
    Deque<Integer> stack = new ArrayDeque<Integer>(graph.n);
    stack.push(s);
    

    while (! stack.isEmpty()) {
      Integer u = stack.pop();
      visited[u] = true;
      for (Integer v : graph.edges.get(u)) {
        if (!visited[v]) {
          stack.push(v);
        }
      }
    }
  }



  public static void main(String args[]) throws Exception {
    boolean recursive = true;
    if (args.length == 1) {
      if (args[0].equals("--nonrec")) {
        recursive = false;
      }
      else if (args[0].equals("--help")) {
        System.err.println("usage: java UndirectedConnectivity [--nonrec | --help]");
        System.err.println("runs dfs on a graph and outputs, for each vertex, whether it is reachable from a start vertex");
        System.exit(-1);
      }
      else {
        System.err.println("unknown option: " + args[1]);
        System.exit(-1);
      }
    }


    Scanner scanner = new Scanner(System.in);
    errPrintln("*** Undirected Connectivity");
    errPrint("number of vertices: ");
    int n = scanner.nextInt();
    Graph graph = new Graph(n);
    errPrint("number of edges: ");
    int m = scanner.nextInt();
    for (int i = 0; i < m; i++) {
      errPrint("enter edge " + (i + 1) + " out of " + m + ": ");
      int u = scanner.nextInt();
      int v = scanner.nextInt();
      graph.addEdge(u, v);
    }
    errPrint("enter edge start vertex for DFS: ");
    int s = scanner.nextInt();

    boolean[] visited = new boolean[n];
    dfsNonrecursive(s, visited, graph);
    errPrintln("reachable from " + s + ": ");
    for (int u = 0; u < n; u++) {
      System.out.println(u + ": " + visited[u]);
    }
  }
}