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



public class BreadthFirstSearch {

    public static boolean[] breadthFirstSearch(int s, Graph graph) {
        Queue<Integer> queue = new ArrayDeque<Integer>();
        queue.add(Integer.valueOf(s));
        boolean visited[] = new boolean[graph.n];
        visited[s] = true;

        while(queue.size() > 0) {
            int u = queue.remove();
            for (int v : graph.edges.get(u)) {
                if (!visited[v]) {
                    visited[v] = true;
                    queue.add(v);
                }
            }
        }
        return visited;
    }
    public static void main(String args[]) throws Exception {
        Scanner scanner = new Scanner (System.in);
        System.err.println("*** Breadth First Search in Undirected Graphs");
        System.err.print("number of vertices: ");
        int n = scanner.nextInt();
        Graph graph = new Graph(n);
        System.err.print("number of edges: ");
        int m = scanner.nextInt();
        for (int i = 0; i < m; i++) {
            System.err.print("enter edge " + (i+1) + " out of " + m + ": ");
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            graph.addEdge(u, v);
        }
        System.err.print("enter edge start vertex for DFS: ");
        int s = scanner.nextInt(); 

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