import java.util.Scanner;
import java.lang.StringBuilder;

class CollectionException extends Exception {
    public CollectionException(String msg) {
        super(msg);
    }
}

interface Collection {
    static final String ERR_MSG_EMPTY = "Collection is empty.";
    static final String ERR_MSG_FULL = "Collection is full.";
    boolean isEmpty();
    boolean isFull();
    int count();
    String toStg();
}

class Deque<T> implements Collection {

    private static final int DEFAULT_CAPACITY = 256;

    @SuppressWarnings("unchecked")
    T[] items = (T[]) new Object[DEFAULT_CAPACITY];
    int front;
    int back;
    int count;

    @SuppressWarnings("unchecked")
    public Deque() {
        T[] items = (T[]) new Object[DEFAULT_CAPACITY];
        int front = 0;
        int back = 0;
        int count = 0;
    }

    public int count() {
        return count;
    }

    public boolean isEmpty() {
        return count == 0;
    }

    public boolean isFull() {
        return count == items.length;
    }

    public String toStg() {
        StringBuilder sb = new StringBuilder("[");
        if (count > 0) {
            sb.append(items[front]);
            for (int i = 1; i < count; i++) {
                sb.append(", ");
                sb.append(items[(front + i) % items.length]);
            }
        }
        sb.append("]");
        return sb.toString();
    }

    public T front() throws CollectionException {
        if (isEmpty())
            throw new CollectionException(ERR_MSG_EMPTY);
        return items[front];
    }

    public T back() throws CollectionException {
        if (isEmpty())
            throw new CollectionException(ERR_MSG_EMPTY);
        return items[(back - 1 + items.length) % items.length];
    }

    public void enqueue(T x) throws CollectionException {
        if (isFull())
            throw new CollectionException(ERR_MSG_FULL);
        items[back] = x;
        back = (back + 1) % items.length;
        count++;
    }

    public void enqueueFront(T x) throws CollectionException {
        if (isFull())
            throw new CollectionException(ERR_MSG_FULL);
        front = (front - 1 + items.length) % items.length;
        items[front] = x;
        count++;
    }

    public T dequeue() throws CollectionException {
        if (isEmpty())
            throw new CollectionException(ERR_MSG_EMPTY);
        T temp = items[front];
        items[front] = null;
        front = (front + 1) % items.length;
        count--;
        return temp;
    }

    public T dequeueBack() throws CollectionException {
        if (isEmpty())
            throw new CollectionException(ERR_MSG_EMPTY);
        T temp = items[(back - 1 + items.length) % items.length];
        items[(back - 1 + items.length) % items.length] = null;
        back = (back - 1 + items.length) % items.length;
        count--;
        return temp;
    }

}

class Edge {

    int v1;
    int v2;

    public Edge(int v1, int v2) {
        this.v1 = v1;
        this.v2 = v2;
    }

}

class Graph {

    public String type;
    public int numVerts;
    public Edge[] edges;

    private String entry;
    private String exit;
    private String order;
    private int[] paths;

    public Graph(String type, int numVerts, Edge[] edges) {
        this.type = type;
        this.numVerts = numVerts;
        this.edges = edges;
    }

    public void walks(int length) {
        int[][] nMatrix = new int[numVerts][numVerts];
        for (int i = 0; i < edges.length; i++) {
            nMatrix[edges[i].v1][edges[i].v2] = 1;
            if (type.equals("undirected"))
                nMatrix[edges[i].v2][edges[i].v1] = 1;
        }
        int[][] walks = nMatrix;
        for (int i = 1; i < length; i++) {
            walks = multiplyMatrices(walks, nMatrix);
        }
        for (int i = 0; i < numVerts; i++) {
            for (int j = 0; j < numVerts; j++) {
                System.out.print(walks[i][j] + " ");
            }
            System.out.println();
        }
    }



    public void dfsFull() {
        boolean[] visited = new boolean[numVerts];
        entry = "";
        exit = "";
        for (int i = 0; i < numVerts; i++) {
            if (!visited[i])
                dfs(i, visited);
        }
        System.out.println(entry);
        System.out.println(exit);
    }

    private void dfs(int v, boolean[] visited) {
        entry += Integer.toString(v) + " ";
        visited[v] = true;
        int[] neighbors = getNeighbors(v);
        for (int i = 0; i < neighbors.length; i++) {
            if (!visited[neighbors[i]])
                dfs(neighbors[i], visited);
        }
        exit += Integer.toString(v) + " ";
    }

    public void bfsFull() throws Exception {
        boolean[] visited = new boolean[numVerts];
        order = "";
        for (int i = 0; i < numVerts; i++) {
            if (!visited[i])
                bfs(i, visited, "bfs");
        }
        System.out.println(order);
    }

    private void bfs(int v, boolean[] visited, String mode) throws Exception {
        Deque<Integer> q = new Deque<Integer>();
        if (mode.equals("sp"))
            paths[v] = 0;
        visited[v] = true;
        q.enqueue(v);
        while (!q.isEmpty()) {
            v = q.dequeue();
            if (mode.equals("bfs"))
                order += v + " ";
            int[] neighbors = getNeighbors(v);
            for (int i = 0; i < neighbors.length; i++) {
                if (!visited[neighbors[i]]) {
                    if (mode.equals("sp"))
                        paths[neighbors[i]] = paths[v] + 1;
                    visited[neighbors[i]] = true;
                    q.enqueue(neighbors[i]);
                }
            }
        }
    }

    public void sp(int v) throws Exception {
        boolean[] visited = new boolean[numVerts];
        order = "";
        paths = new int[numVerts];
        for (int i = 0; i < numVerts; i++) {
            paths[i] = -1;
        }
        bfs(v, visited, "sp");
        for (int i = 0; i < numVerts; i++) {
            System.out.println(i + " " + paths[i]);
        }
    }

    private int[][] multiplyMatrices(int[][] m1, int[][] m2) {
        int[][] multipliedMatrix = new int[m1.length][m1.length];
        int sum = 0;
        for (int i1 = 0; i1 < m1.length; i1++) {
            for (int i2 = 0; i2 < m2[0].length; i2++) {
                for (int j = 0; j < m1[0].length; j++) {
                    sum += m1[i1][j] * m2[j][i2];
                }
                multipliedMatrix[i1][i2] = sum;
                sum = 0;
            }
        };
        return multipliedMatrix;
    }

    private int countOccurences(int element) {
        int counter = 0;
        for (int i = 0; i < edges.length; i++) {
            if (type.equals("directed")) {
                if (edges[i].v1 == element)
                    counter++;
            } else {
                if (edges[i].v1 == element || edges[i].v2 == element) {
                    counter++;
                }
            }
        }
        return counter;
    }

    private int[] getNeighbors(int v) {
        int[] neighbors = new int[countOccurences(v)];
        int index = 0;
        for (int i = 0; i < edges.length; i++) {
            if (edges[i].v1 == v) {
                neighbors[index] = edges[i].v2;
                index++;
            }
            if (type.equals("undirected")) {
                if (edges[i].v2 == v) {
                    neighbors[index] = edges[i].v1;
                    index++;
                }
            }
        }
        insertionSort(neighbors);
        return neighbors;
    }

    private void insertionSort(int[] array) {
        int temp;
        for (int i = 1; i < array.length; i++) {
            temp = array[i];
            for (int j = i; j > 0; j--) {
                if (array[j - 1] > temp) {
                    array[j] = array[j - 1];
                    array[j - 1] = temp;
                } else {
                    array[j] = temp;
                    break;
                }
            }
        }
    }

}

public class Naloga3 {

    public static void main(String[] args) throws Exception {
        String graphType = args[0];
        Scanner sc = new Scanner(System.in);
        int numVerts = Integer.parseInt(sc.nextLine().trim());
        StringBuilder sb1 = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();
        while (sc.hasNextLine()) {
            String[] line = sc.nextLine().trim().split(" ");
            sb1.append(line[0] + ":");
            sb2.append(line[1] + ":");
        }
        String[] v1 = sb1.toString().split(":");
        String[] v2 = sb2.toString().split(":");
        Edge[] edges = new Edge[v1.length];
        for (int i = 0; i < v1.length; i++) {
            edges[i] = new Edge(Integer.parseInt(v1[i]), Integer.parseInt(v2[i]));
        }
        Graph g = new Graph(graphType, numVerts, edges);
        switch (args[1]) {
            case "walks":   g.walks(Integer.parseInt(args[2]));
                            break;
            case "dfs":     g.dfsFull();
                            break;
            case "bfs":     g.bfsFull();
                            break;
            case "sp":      g.sp(Integer.parseInt(args[2]));
                            break;
        }
    }

}