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
Output
Constraints
You can choose the walk to get a gcd of 2