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

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 main(String args[]) throws Exception {
    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];
    depthFirstSearch(s, visited, graph);
    errPrintln("reachable from " + s + ": ");
    for (int u = 0; u < n; u++) {
      System.out.println(u + ": " + visited[u]);
    }
  }
}