minimalCost.cpp

#include <bits/stdc++.h>

using namespace std;

#define int long long 
#define what_is(a) cout << #a << " is " << a << "\n"
#define checker(a) cout << "checker reached " << a << "\n"

inline void io(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

int arr[100009];
vector<vector<int>> adj(100009,vector<int>());
int freq[100009];
int v[100009];

bool comp(int a,int b){
    return freq[a] < freq[b];
} 

int ans = INT_MAX;

void dfs(int u,int gcd){
    int r = __gcd(arr[u],gcd);
    //cout << arr[u] << " " << gcd << "\n";
    ans = min(ans,r);
    v[u] = 1;
    for(int x:adj[u])
        if(v[x])continue;
        else{
            dfs(x,r);
        }           
}

int solve(){
    int n,m;
    cin >> n >> m;
    for(int i=0;i<n;i++)
        cin >> arr[i];
    while(m--){
        int a,b;
        cin >> a >> b;
        a--,b--;
        adj[a].push_back(b);
        freq[b]++;
    }
    vector<int> vec;
    for(int i=0;i<n;i++)
         vec.push_back(i);
    sort(vec.begin(),vec.end(),comp);
    for(int u:vec){
        if(v[u]==0)
        dfs(u,arr[u]);
    }
    memset(v,0,sizeof(v));
    for(int i=0;i<n;i++)
        if(v[i]==0)
            dfs(i,arr[i]);
    memset(v,0,sizeof(v));
    for(int i=n-1;i>=0;i--)
        if(v[i]==0)
            dfs(i,arr[i]);
    cout << ans << "\n";
    return 0;
}

signed main(){
    io();
    int t = 1;
    while(t--){
        solve();
    }
    return 0;
}