codeforces498C

Array and Operations

You have written on a piece of paper an array of n positive integers a[1], a[2], ..., a[n] and m good pairs of integers (i₁, j₁), (i₂, j₂), ..., (i_m, j_m). Each good pair (i_k, j_k) meets the following conditions: i_k + j_k is an odd number and 1 ≤ i_k < j_k ≤ n.

In one operation you can perform a sequence of actions:

take one of the good pairs (i_k, j_k) and some integer v (v > 1), which divides both numbers a[i_k] and a[j_k];
divide both numbers by v, i. e. perform the assignments: $\text{[math]}$ and $\text{[math]}$ .

Determine the maximum number of operations you can sequentially perform on the given array. Note that one pair may be used several times in the described operations.

Input

The first line contains two space-separated integers n, m (2 ≤ n ≤ 100, 1 ≤ m ≤ 100).

The second line contains n space-separated integers a[1], a[2], ..., a[n] (1 ≤ a[i] ≤ 10⁹) — the description of the array.

The following m lines contain the description of good pairs. The k-th line contains two space-separated integers i_k, j_k (1 ≤ i_k < j_k ≤ n, i_k + j_k is an odd number).

It is guaranteed that all the good pairs are distinct.

Output

Output the answer for the problem.

Examples

Input

Output

Input

Output

2

sol：看到两个坐标相加一定是奇数，而且这个数据范围100,100，容易联想到网络流，而且分组就是下标奇偶分成两组。
建图就呼之欲出了，对于每个质因数建一张图，源点S向每个奇数下标连上那个数字中那个质因数个数，同理偶数下标向汇点T连边，对于奇偶之间就连上他们质因数个数的较小值

#include <bits/stdc++.h>
using namespace std;
typedef int ll;
inline ll read()
{
    ll s=0;
    bool f=0;
    char ch=' ';
    while(!isdigit(ch))
    {
        f|=(ch=='-'); ch=getchar();
    }
    while(isdigit(ch))
    {
        s=(s<<3)+(s<<1)+(ch^48); ch=getchar();
    }
    return (f)?(-s):(s);
}
#define R(x) x=read()
inline void write(ll x)
{
    if(x<0)
    {
        putchar('-'); x=-x;
    }
    if(x<10)
    {
        putchar(x+'0');    return;
    }
    write(x/10);
    putchar((x%10)+'0');
    return;
}
#define W(x) write(x),putchar(' ')
#define Wl(x) write(x),putchar('
')
const int N=205,M=1005,inf=0x3f3f3f3f;
int n,m,a[N],Ges[N];
int S,T;
struct Edge
{
    int U,V;
}E[N];
int Prim[100005];
bool Bo[100005];
inline void Shai(int Up)
{
    int i,j;
    Bo[0]=Bo[1]=1;
    for(i=2;i<=Up;i++)
    {
        if(!Bo[i]) Prim[++*Prim]=i;
        for(j=1;j<=*Prim&&i*Prim[j]<=Up;j++)
        {
            Bo[i*Prim[j]]=1; if(i%Prim[j]==0) break;
        }
    }
}
namespace Picture
{
    int tot=0,Next[M],to[M],Val[M],head[N];
    
    inline void Init();
    inline void add(int x,int y,int z);
    inline bool bfs(int S);
    inline int dfs(int S,int T,int Dist);
    inline int Max_Flow();
    
    inline void Init()
    {
        tot=0;
        memset(head,0,sizeof head);
    }
    inline void add(int x,int y,int z)
    {
        Next[++tot]=head[x];
        to[tot]=y;
        Val[tot]=z;
        head[x]=tot;
        
        Next[++tot]=head[y];
        to[tot]=x;
        Val[tot]=0;
        head[y]=tot;
    }
    int Depth[N];
    inline bool bfs(int S)
    {
        memset(Depth,0,sizeof Depth);
        int i;
        queue<int>Queue;
        while(!Queue.empty()) Queue.pop();
        Depth[S]=1;
        Queue.push(S);
        while(!Queue.empty())
        {
            int x=Queue.front(); Queue.pop();
            for(i=head[x];i;i=Next[i]) if(Val[i]>0&&Depth[to[i]]==0)
            {
                Depth[to[i]]=Depth[x]+1;
                Queue.push(to[i]);
            }
        }
        return (Depth[T]==0)?0:1;
    }
    inline int dfs(int x,int Dist)
    {
        if(x==T) return Dist;
        int i;
        for(i=head[x];i;i=Next[i])
        {
            if(Depth[to[i]]==Depth[x]+1&&Val[i]>0)
            {
                int oo=dfs(to[i],min(Dist,Val[i]));
                if(oo>0)
                {
                    Val[i]-=oo;
                    (i&1)?Val[i+1]+=oo:Val[i-1]+=oo;
                    return oo;
                }
            }
        }
        return 0;
    }
    inline int Max_Flow()
    {
        int ans=0;
        while(bfs(S))
        {
            ans+=dfs(S,inf);
        }
        return ans;
    }
}
#define Pic Picture
int main()
{
    int i,j,ans=0;
    R(n); R(m);
    S=0; T=n+1;
    for(i=1;i<=n;i++) R(a[i]);
    for(i=1;i<=m;i++)
    {
        R(E[i].U); R(E[i].V);
        if(E[i].U%2==0) swap(E[i].U,E[i].V);
    }
    Shai(100000);
    for(i=1;i<=*Prim;i++)
    {
        memset(Ges,0,sizeof Ges);
        Pic::Init();
        for(j=1;j<=n;j++)
        {
            while(a[j]%Prim[i]==0)
            {
                a[j]/=Prim[i]; Ges[j]++;
            }
        }
        for(j=1;j<=n;j++)
        {
            if(j&1) Pic::add(S,j,Ges[j]);
            else Pic::add(j,T,Ges[j]);
        }
        for(j=1;j<=m;j++)
        {
            Pic::add(E[j].U,E[j].V,min(Ges[E[j].U],Ges[E[j].V]));
        }
        ans+=Pic::Max_Flow();
    }
    Pic::Init();
    for(i=1;i<=n;i++) if(a[i]!=1)
    {
        if(i&1) Pic::add(S,i,1);
        else Pic::add(i,T,1);
    }
    for(i=1;i<=m;i++) if(a[E[i].U]==a[E[i].V]&&a[E[i].U]!=1)
    {
        Pic::add(E[i].U,E[i].V,1);
    }
    ans+=Pic::Max_Flow();
    Wl(ans);
    return 0;
}
/*
Input
3 2
8 3 8
1 2
2 3
Output
0

Input
3 2
8 12 8
1 2
2 3
Output
2
*/

View Code