#include <iostream>
#include <vector>
#include <climits>
using namespace std;

void solve(int n, int m, int S, int A, int B, vector<pair<int, int>>& edges, int c)
{
    // Initializare matrice de distante
    vector<vector<int>> dist(n + 1, vector<int>(n + 1, INT_MAX / 2));

    for (int i = 1; i <= n; ++i) {
        dist[i][i] = 0;
    }

    for (const auto& edge : edges) {
        int x = edge.first;
        int y = edge.second;
        dist[x][y] = 1;
    }

    // Algoritmul Floyd-Warshall
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }

    for(int i = 1; i<=n; i++){
        for(int j = 1; j<=n; j++)
            cout << dist[i][j] << ' ';
        cout << endl;
    }

    // Găsirea ciclurilor de lungime 2
    int min_cycle = INT_MAX;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (dist[i][j] != INT_MAX / 2 && dist[j][i] != INT_MAX / 2 && i != j) {
                min_cycle = min(min_cycle, dist[i][j] + dist[j][i]);
            }
        }
    }

    // Cazul 1: Afisare valoare minima
    if (c == 1) {
        int result = min(min_cycle, dist[S][A] + dist[S][B]);
        cout << result << endl;
    }
    // Cazul 2: Afisare drumuri
    else {
        // Găsirea soluției optime pentru conectarea nodurilor
        int result = min(min_cycle, min(dist[S][A] + dist[A][B] + dist[B][S], dist[S][B] + dist[B][A] + dist[A][S]));

        if (result == min_cycle) {
            // Nu trebuie să conectăm cele două noduri de start
            cout << min_cycle << endl;
        } else if (result == dist[S][A] + dist[A][B] + dist[B][S]) {
            // Conectăm nodurile în ordinea S -> A -> B
            cout << dist[S][A] + 2 + dist[B][S] << endl;
            cout << S << " " << A << endl;
            cout << A << " " << B << " " << S << endl;
        } else {
            // Conectăm nodurile în ordinea S -> B -> A
            cout << dist[S][B] + 2 + dist[A][S] << endl;
            cout << S << " " << B << endl;
            cout << B << " " << A << " " << S << endl;
        }
    }
}

int main() {
    int c, n, m, S, A, B;
    cin >> c >> n >> m >> S >> A >> B;

    vector<pair<int, int>> edges(m);
    for (int i = 0; i < m; ++i) {
        cin >> edges[i].first >> edges[i].second;
    }

    // Apelare functie de rezolvare
    solve(n, m, S, A, B, edges, c);

    return 0;
}