对于无向图 ,它的任一棵生成树 的权值 定义为 的所有边权的最大公约数。
对于给定的图 ，求出其所有生成树 ……的权值 ……的最小公倍数。
第一行N M 表示图G的点数，边数。
接下来M行 描述一条边（）权值为 。
保证图连通，无自环。
一个数，所有生成树权值的最小公倍数。
样例输入
3 3 1 2 2 2 3 3 1 3 6
样例输出
6
【样例说明】有3棵生成树，权值分别为1,2,3,它们的最小公倍数为6。
【数据规模】