#include<bits/stdc++.h>

#define F first
#define S second
#define pb push_back

using namespace std;
int main() {
    unordered_map < string, int > nom;
    vector < int > ot;
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    int n, m;
    cin >> n >> m;
    string t[n];
    for (int i = 0; i < n; ++i) {
        cin >> t[i];
        nom[t[i]] = i;
    }
    vector < vector < int > > g(n);
    for (int i = 0; i < m; ++i) {
        int x, y;
        cin >> x >> y;
        --x;
        --y;
        g[x].pb(y);
        g[y].pb(x);
    }
    vector < string > r(n);
    r[0] = t[0] + '|';
    priority_queue < pair < int, int > > q;
    q.push({-r[0].size(), 0});
    while (!q.empty()) {
        int v = q.top().S, w = -q.top().F;
        q.pop();
        if (r[v].size() != w) continue;
        for (auto to : g[v])
            if (r[to].empty() || (r[to].size() > w + t[to].size() + 1) || (r[to].size() == w + t[to].size() + 1 && r[to] > r[v] + t[to] + '|')) {
                r[to] = r[v] + t[to] + '|';
                q.push({-r[to].size(), to});
            }
    }
//    cout << r[n - 1];
//    return 0;
    string now;
    for (int i = 0; i < r[n - 1].size(); ++i)
        if (r[n - 1][i] == '|') {
        ot.pb(nom[now] + 1);
        now.clear();
    }
    else now += r[n - 1][i];
    cout << ot.size() << '\n';
    for (int i = 0; i < ot.size(); ++i)
        cout << ot[i] << ' ';
    return 0;
}