import java.util.Scanner;


@SuppressWarnings("serial")
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 Edge {

    int vert1; int vert2;

    public Edge(int v1, int v2) {
        this.vert1 = v1; this.vert2 = v2;
    }
}
//copy of snipsets of Naloga1
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() {
        @SuppressWarnings("unused")
        T[] items = (T[]) new Object[DEFAULT_CAPACITY];
        @SuppressWarnings("unused")
        int front = 0;
        @SuppressWarnings("unused")
        int back = 0;
        @SuppressWarnings("unused")
        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 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[][] matrix = new int[numVerts][numVerts];
        for (int i = 0; i < edges.length; i++) {
            matrix[edges[i].vert1][edges[i].vert2] = 1;
            if (type.equals("undirected"))
                matrix[edges[i].vert2][edges[i].vert1] = 1;
        }
        int[][] walks = matrix;
        for (int i = 1; i < length; i++) {
            walks = multiplyMatrices(walks, matrix);
        }
        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 i = 0; i < m1.length; i++) {
            for (int j = 0; j < m2[0].length; j++) {
                for (int k = 0; k < m1[0].length; k++) {
                    sum += m1[i][k] * m2[k][j];
                }
                multipliedMatrix[i][j] = 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].vert1 == element)
                    counter++;
            } else {
                if (edges[i].vert1 == element || edges[i].vert2 == 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].vert1 == v) {
                neighbors[index] = edges[i].vert2;
                index++;
            }
            if (type.equals("undirected")) {
                if (edges[i].vert2 == v) {
                    neighbors[index] = edges[i].vert1;
                    index++;
                }
            }
        }
        insertionSort(neighbors);
        return neighbors;
    }

    private void insertionSort(int arr[])
    {
        int n = arr.length;
        for (int i=1; i<n; ++i)
        {
            int key = arr[i];
            int j = i-1;

            /* Move elements of arr[0..i-1], that are
               greater than key, to one position ahead
               of their current position */
            while (j>=0 && arr[j] > key)
            {
                arr[j+1] = arr[j];
                j = j-1;
            }
            arr[j+1] = key;
        }
    }

}
/**
 * @author Jure Zajc
 *
 */
public class Naloga3 {

    /**
     * @param args
     * @throws Exception
     */
    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub

        @SuppressWarnings("resource")
        Scanner scanner = new Scanner(System.in);
        String gType = scanner.next();
        int nVerts = Integer.parseInt(scanner.nextLine().trim());
        StringBuilder sb = new StringBuilder();
        StringBuilder sb1 = new StringBuilder();
        while (scanner.hasNextLine()) {
            String[] line = scanner.nextLine().trim().split(" ");
            sb.append(line[0] + ":");
            sb1.append(line[1] + ":");
        }
        String[] vert1 = sb.toString().split(":");
        String[] vert2 = sb1.toString().split(":");
        Edge[] edges = new Edge[vert1.length];
        for (int i = 0; i < vert1.length; i++) {
            edges[i] = new Edge(Integer.parseInt(vert1[i]), Integer.parseInt(vert2[i]));
        }
        Graph graph = new Graph(gType, nVerts, edges);
        switch(scanner.next()){
        case "walks":   graph.walks(Integer.parseInt(scanner.next())); break;
        case "dfs":     graph.dfsFull(); break;
        case "bfs":     graph.bfsFull();break;
        case "sp":      graph.sp(Integer.parseInt(scanner.next())); break;
        }
    }
}