f.cpp

#include <bits/stdc++.h>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long

#define IOS ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

using namespace std;
const int INF = 1e9 + 1;
const int MOD = 1e9 + 7;
const int MAXN = 1e6 + 10;
int min_div[MAXN + 10], a[MAXN], pos[MAXN];
map <int, int> cnt;
vector <int> prime_divs[MAXN + 10], primes, g[MAXN];
bool was[MAXN];
int dist[MAXN], pr[MAXN];
void solve(){

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    int m = n;
    for (int x : primes){
        m++;
        a[m] = x;
        pos[x] = m;
    }
    for (int i = 1; i <= n; i++){
        for (int x : prime_divs[a[i]]){
            g[i].pb(pos[x]);
            g[pos[x]].pb(i);
        }
    }

    queue <int> q;
    int s, t;
    cin >> s >> t;
    q.push(s);
    was[s] = 1;
    dist[s] = 0;
    pr[s] = -1;

    while(!q.empty()){
        int v = q.front();
        q.pop();

        for (int to : g[v]){
            if (!was[to]){
                was[to] = 1;
                dist[to] = dist[v] + 1;
                q.push(to);
                pr[to] = v;
            }
        }
    }
    if (!was[t]){
        cout << -1 << '\n';
    }
    else{
        int x = t;
        vector <int> ans;
        while (x != -1){
            ans.pb(x);
            x = pr[x];
        }
        reverse(ans.begin(), ans.end());
        cout << dist[t] / 2 + 1 << '\n';
        for (int i = 0; i < ans.size(); i++){
            if (i % 2 == 0){
                cout << ans[i] << ' ';
            }
        }
        cout << '\n';

    }

}

int main() {
    IOS;
    int t = 1;
    //cin >> t;

    for (int i = 2; i <= MAXN; i++){
        if (prime_divs[i].size() == 0){
            prime_divs[i].pb(i);
            primes.pb(i);
            for (int j = i + i; j <= MAXN; j += i){
                prime_divs[j].pb(i);
            }
        }
    }

    while(t--){
        solve();
    }
    return 0;
}