#include <bits/stdc++.h>
#define nmax 100010
#define oo 1e13

using namespace std;

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

struct fact
{
    long long baza;
    int exp;
};

class cmp
{
public:
    const bool operator() ( const pair<int, int> &a, const pair<int, int> &b )
    {
        return a.second > b.second;
    }
};

vector <fact> factprim;
vector <int> graf[nmax];
vector <int> drum;
long long val[nmax], pret[nmax], ans, k;
int n, m, cur[nmax], vecin[nmax];

void factorizare( long long x )
{
    for ( int i = 2; i*i <= x; ++i )
    {
        if ( x%i == 0 )
            factprim.push_back({i, 0});
        while ( x%i == 0 )
        {
            factprim.back().exp++;
            x /= i;
        }
    }
    if ( x > 1 )
        factprim.push_back({x, 1});
}

priority_queue <pair<int, int>, vector<pair<int, int>>, cmp> Q;

long long dijkstra ( int pos )
{
    for ( int i = 2; i <= n; ++i )
        pret[i] = oo;
    for ( int i = 1; i <= n; ++i )
        cur[i] = val[i];
    Q.push({1, 0});
    while ( Q.size() )
    {
        int nod = Q.top().first;
        int cost = Q.top().second;
        Q.pop();
        if ( cost == pret[nod] )
        {
            while ( cur[nod]%factprim[pos].baza == 0 )
            {
                cur[nod] /= factprim[pos].baza;
                cost++;
            }
            for ( auto x : graf[nod] )
            {
                if ( cost < pret[x] )
                {
                    vecin[x] = nod;
                    pret[x] = cost;
                    Q.push({x, cost});
                }
            }
        }
    }
    while ( val[n]%factprim[pos].baza == 0 )
    {
        val[n] /= factprim[pos].baza;
        pret[n]++;
    }
    return pret[n]/factprim[pos].exp;
}

int main()
{
    ans = oo;
    fin>>n>>m>>k;
    for ( int i = 1; i <= n; ++i )
        fin>>val[i];
    for ( int i = 1; i <= m; ++i )
    {
        int x, y;
        fin>>x>>y;
        graf[x].push_back(y);
    }
    factorizare(k);
    for ( int i = 0; i < factprim.size(); ++i )
    {
        long long pret = dijkstra(i);
        if ( ans > pret )
        {
            ans = pret;
            drum.clear();
            int nod = n;
            while ( nod )
            {
                drum.push_back(nod);
                nod = vecin[nod];
            }
        }
    }
    fout<<ans<<'\n';
    for ( int i = drum.size()-1; i >= 0; --i )
        fout<<drum[i]<<" ";
}