GCD on directed graph

3.5

18 votes
Algorithms, Graphs, Greatest common divisor, Medium, Sieve, gcd, scc
Problem

You are given a directed graph with n nodes and m edges. The nodes are numbered from 1 to n, and node i is assigned a cost . The cost of a walk on the graph is defined as the greatest common divisor of the costs of the vertices used in the walk. Formally, the cost of a walk is given by . Note that 's need not be distinct. Find the cost of the walk with minimum cost.

The walk might consist of single vertex.

Input

  • The first line contains two integers, n, and m.
  • The next line contains n space separated integers, of which is equal to
  • Each of the next m lines contain two integers, u, and v, denoting a directed edge from u to v.

Output

  • Print one integer containing the cost of the walk with minimum cost.

Constraints

Sample Input
3 2
4 6 8
1 2
2 3
Sample Output
2
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

You can choose the walk to get a gcd of 2

Editor Image

?