#include <bits/stdc++.h>

using namespace std;

#define pb push_back
#define mk make_pair


typedef long long ll;

const int Z = 1111;
const int inf = int(1e9) + 123;
const ll llinf = ll(1e18) + 123;

vector <pair<int, pair<int,string>>> g[Z];
int a[Z];
string c[Z];
int d[Z], pr[Z];

int main () {
    ios_base::sync_with_stdio(false);
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
        a[i] = c[i].size();
    }
    for (int i = 1; i <= m; i++) {
        int x, y;
        cin >> x >> y;
        g[x].pb(mk(y, mk(a[y], c[y])));
        g[y].pb(mk(x, mk(a[x], c[x])));
    }
    fill (d + 1, d + 1 + n, inf);
    set <pair<int, pair<int,string>>> mn;
    int start = 1;
    d[start] = 0;
    mn.insert(mk(d[start], mk(start,"")));
    while (!mn.empty()) {
        int v = (mn.begin() -> second).first;
        mn.erase(mn.begin());
        for (int i = 0; i < g[v].size(); i++) {
            int to = g[v][i].first;
            int w = g[v][i].second.first;
            string l = g[v][i].second.second;
            if (d[to] >= d[v] + w) {
                if (d[to] > d[v] + w) {
                    mn.erase(mk(d[to],mk(to,c[to])));
                    d[to] = d[v] + w;
                    mn.insert(mk(d[to], mk(to, c[v])));
                    pr[to] = v;
                } else {
                    if (c[to] > c[v]) {
                    mn.erase(mk(d[to],mk(to,c[to])));
                    d[to] = d[v] + w;
                    mn.insert(mk(d[to], mk(to, c[v])));
                    pr[to] = v;
                    }
                }
            }
        }
    }
    vector <int> ans;
    int p = n;
    while (p != 1) {
        ans.push_back(p);
        p = pr[p];
    }
    ans.push_back(1);
    reverse(ans.begin(), ans.end());
    cout << ans.size() << "\n";
    for (int x : ans) {
        cout << x << ' ';
    }
    return 0;
}#incl