#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize ("O3")
#pragma GCC optimizeation ("Ofast")


ifstream fin("ceva.in");
ofstream fout ("ceva.out");

int c, n, m, start, a, b, tata[10001], viz[10001], viz3[10001], v3[10001], viz1[10001], v1[10001], v[10001];
int merg_invers[10001], nr_invers, merg[10001], nr;
vector <int> g[10001], G[10001];
queue <pair <int, int >> coada;

void bfs1 () {
  queue <int> Q;

  Q.push(start);
  viz[start] = 1;

  tata[start] = start;
  while (!Q.empty()) {
    int k = Q.front();
    Q.pop();

    for (int i : g[k]) {
      if (!viz[i]) {
        v[i] = v[k] + 1;
        tata[i] = k;
        viz[i] = 1;
        Q.push(i);
      }
    }
  }
}

void bfs2 (int pornire) {
  queue <int> Q;

  Q.push(pornire);

  viz1[pornire] = 1;

  while (!Q.empty()) {
    int k = Q.front();
    Q.pop();

    for (int i : g[k]) {
      if (!viz1[i]) {
        viz1[i] = 1;
        v1[i] = v1[k] + 1;
        Q.push(i);
      }
    }
  }
}

void bfs3 (int pornire) {
  queue <int> Q;

  Q.push(pornire);

  viz3[pornire] = 1;

  while (!Q.empty()) {
    int k = Q.front();
    Q.pop();

    for (int i : g[k]) {
      if (!viz3[i]) {
        viz3[i] = 1;
        v3[i] = v3[k] + 1;
        Q.push(i);
      } else if (i == pornire){
        coada.push({i, v3[k] + v[pornire] + 1});
        return;
      }
    }
  }
}

int viz4[10001], v4[10001], daddy[10001], exista, viz5[10001], mommy[10001];
void bfs4 (int porneste) {
  queue <int> Q;

  Q.push(porneste);
  viz4[porneste] = 1;
  daddy[porneste] = porneste;
  while (!Q.empty()) {
    int k = Q.front();

    Q.pop();

    for (int i : g[k]) {
      if (!viz4[i]) {
        viz4[i] = 1;
        v4[i] = v4[k] + 1;
        daddy[i] = k;
        Q.push(i);
      } else if (i == porneste) {
        exista = k;

        return;
      }
    }
  }
}


void bfs5 (int porneste) {
  queue <int> Q;

  Q.push(porneste);
  viz5[porneste] = 1;
  mommy[porneste] = porneste;

  while (!Q.empty()) {
    int k = Q.front();

    for (int i : g[k]) {
      if (!viz5[i]) {
        viz5[i] = 1;
        mommy[i] = k;
        Q.push(i);
      }
    }

    Q.pop();
  }
}

int main () {

  fin >> c >> n >> m >> start >> a >> b;

  for (int i = 1; i <= m; i++) {
    int x, y;

    fin >> x >> y;

    g[x].push_back(y);
    G[y].push_back(x);
  }

  if (c == 1) {
    bfs1();

    for (int i = 1; i <= n; i++) {
      bfs3(i);

      for (int j = 1; j <= n; j++) {
        viz3[j] = 0;
        v3[j] = 0;
      }
    }

    int minim = 100000001;
    while (!coada.empty()) {
      int ceva = coada.front().first;
      int bengos = coada.front().second;
      coada.pop();

      bfs2(ceva);

      minim = min(max(bengos + v1[a], v1[b] + bengos), minim);
      for (int i = 1; i <= n; i++) {
        viz1[i] = 0;
        v1[i] = 0;
      }
    }

    fout << minim;

    return 0;
  }

  bfs1();
  for (int i = 1; i <= n; i++) {
    bfs3(i);

    for (int j = 1; j <= n; j++) {
      viz3[j] = 0;
      v3[j] = 0;
    }
  }

  int minim = 100000001;
  int ciclat;
   while (!coada.empty()) {
      int ceva = coada.front().first;
      int bengos = coada.front().second;
      coada.pop();

      bfs2(ceva);

      int suma = max(bengos + v1[a], bengos + v1[b]);

      if (suma < minim) {
        minim = suma;

        ciclat = ceva;
      }


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

    int nod = ciclat;
    while (nod != start) {
      merg_invers[++nr_invers] = nod;

      nod = tata[nod];
    }

    merg_invers[++nr_invers] = nod;

    for (int i = nr_invers; i >= 1; i--) {
      merg[nr_invers - i + 1] = merg_invers[i];
    }

    nr = nr_invers;

    bfs4(ciclat);

    for (int i = 1; i <= nr; i++) {
      merg_invers[i] = 0;
    }

    nod = exista;

    nr_invers = 0;
    while (nod != ciclat) {
      merg_invers[++nr_invers] = nod;

      nod = daddy[nod];
    }

    for (int i = nr_invers; i >= 1; i--) {
      merg[++nr] = merg_invers[i];
    }

    merg[++nr] = ciclat;

    fout << nr - 1<< '\n';

    for (int i = 1; i <= nr; i++) {
      fout << merg[i] << " ";
    }

    fout << '\n';

    bfs5(ciclat);

    nod = a;
    nr_invers = 0;
    while (nod != ciclat) {
      merg_invers[++nr_invers] = nod;


      nod = mommy[nod];
    }

    merg_invers[++nr_invers] = ciclat;

    nr = nr_invers;

    for (int i = nr_invers; i >= 1; i--) {
      merg[nr_invers - i + 1] = merg_invers[i];
    }

    fout << nr - 1 << '\n';

    for (int i = 1; i <= nr; i++) {
      fout << merg[i] << ' ';
    }

    fout << '\n';

    nod = b;
    nr_invers = 0;
    while (nod != ciclat) {
      merg_invers[++nr_invers] = nod;


      nod = mommy[nod];
    }

    merg_invers[++nr_invers] = ciclat;

    nr = nr_invers;

    for (int i = nr_invers; i >= 1; i--) {
      merg[nr_invers - i + 1] = merg_invers[i];
    }

    fout << nr - 1 << '\n';

    for (int i = 1; i <= nr; i++) {
      fout << merg[i] << ' ';
    }

  return 0;
}