## Graph Theory 5

View as PDF

Points: 7
Time limit: 4.0s
Memory limit: 64M

Author:
Problem types

Given a connected graph of $$N$$ nodes and $$M$$ weighted bidirectional edges, print the maximum Greatest Common Divisor (GCD) of the weights of the edges of any connected subgraph. A connnected subgraph is a graph such that there is at least $$1$$ path between any two nodes, and all edges in the subgraph are in the original graph.

#### Input Specification

The first line will contain two integers, $$N, M\ (2 \le N \le 10^4, 1 \le M \le 10^5)$$.

The next $$M$$ lines will each contain three integers, $$u, v, w\ (1 \le u, v \le N, u \neq v, 1 \le w \le 10^3)$$. There may be more than one edge between any two nodes.

#### Output Specification

Output the maximum GCD of the weights of the edges of any subgraph that can be constructed with the $$M$$ edges.

#### Sample Input

4 5
1 3 3
3 4 8
1 4 4
1 2 6
2 4 12

#### Sample Output

4