All Tracks Algorithms Graphs Strongly Connected Components Problem

GCD on directed graph
Tag(s):

Algorithms, Graph, Greatest common divisor, Greatest common divisor, Medium-Hard, Sieve, gcd, scc

Problem
Editorial
Analytics

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 \(c_i\). 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 \(v_1, v_2, \cdots, v_k \) is given by \(\text{gcd} ( c_{v_1}, c_{v_2}, \cdots, c_{v_k} ) \). Note that \(v_i\)'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, \(i^{\text{th} } \) of which is equal to \(c_i\)
  • 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

  • \(1 \le n, m, c_i \le 10^5 \)
SAMPLE INPUT
3 2
4 6 8
1 2
2 3
SAMPLE OUTPUT
2
Explanation

You can choose the walk \( 1 \rightarrow 2 \rightarrow 3 \) to get a gcd of 2

Time Limit: 1,0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

August Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
Уведомления
View All Notifications

?