import java.io.*;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.StringTokenizer;

public class CountingStar {
    static class FastScanner {
        BufferedReader br;
        StringTokenizer st;

        public FastScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }
    }

    static class DirectedEdge {
        int from;
        int to;
        int c;
        int flow;
        DirectedEdge reversedEdge;
        boolean visited = false;

        public DirectedEdge(int from, int to, int c) {
            this.from = from;
            this.to = to;
            this.c = c;
            this.flow = 0;
            reversedEdge = null;
        }
    }

    static class Query {
        int a;


        int b;

        public Query(int a, int b, int c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }

        int c;

    }

    static class Ship {
        int number;

        public Ship(int number, int to) {
            this.number = number;
            this.to = to;
        }

        int to;
    }

    public static void main(String[] args) {
        FastScanner scanner = new FastScanner();
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int k = scanner.nextInt();
        int source1 = scanner.nextInt() - 1;
        int sink1 = scanner.nextInt() - 1;
        ArrayDeque<Integer>[] to1 = new ArrayDeque[n];
        for (int i = 0; i < n; i++) {
            to1[i] = new ArrayDeque<>();
        }
        for (int i = 0; i < m; i++) {
            int a = scanner.nextInt() - 1;
            int b = scanner.nextInt() - 1;
            to1[a].addLast(b);
            to1[b].addLast(a);
        }
        int L = shortestPath(to1, source1, sink1);
        ArrayDeque<Query> queries = new ArrayDeque<>();

        for (int i = 0; i < (L + k - 1); i++) {
            for (int j = 0; j < n; j++) {
                queries.addLast(new Query(i * n + j, (i + 1) * n + j, Integer.MAX_VALUE));
                for (int to : to1[j]
                ) {
                    queries.addLast(new Query(i * n + j, (i + 1) * n + to, 1));
                }
            }
            int level = i + 1;
            if (level >= L) {
                int source = source1;
                int sink = level * n + sink1;
                ArrayDeque<DirectedEdge>[] to = new ArrayDeque[level * n + n];
                for (int j = 0; j < to.length; j++) {
                    to[j] = new ArrayDeque<>();
                }
                for (Query query : queries) {
                    int a = query.a;
                    int b = query.b;
                    int c = query.c;
                    DirectedEdge edge1 = new DirectedEdge(a, b, c);
                    DirectedEdge reversedEdge1 = new DirectedEdge(b, a, 0);
                    edge1.reversedEdge = reversedEdge1;
                    reversedEdge1.reversedEdge = edge1;
                    to[a].addLast(edge1);
                    to[b].addLast(reversedEdge1);
                }
                boolean[] mark = new boolean[to.length];
                int maxFlow = 0;
                while (true) {
                    Arrays.fill(mark, false);
                    int delta = dfs(source, Integer.MAX_VALUE, mark, to, sink);
                    if (delta > 0) {
                        maxFlow += delta;
                        if (maxFlow >= k) break;
                    } else {
                        break;
                    }
                }
                if (maxFlow >= k) {