#P18398. Many Many Cycles
Many Many Cycles
Many Many Cycles
给定一个无向图 ,求最大的正整数 ,使得图中所有简单环的长度都能被 整除。如果不存在这样的最大整数,输出 0。
环的长度是其中各条边长度之和。简单环不重复经过顶点,除了首尾是同一个顶点。
输入格式
第一行包含两个整数 ,分别表示顶点数和边数:
接下来 行,每行包含三个整数 ,表示顶点 之间有一条长度为 的无向边:
保证图中没有自环和重边。图不一定连通。
输出格式
输出一个整数,表示答案。
若图中没有简单环,任何正整数都满足整除条件,因而不存在最大的一个,此时按要求输出 0。
原样例 1
4 4
1 2 1
2 3 1
3 4 1
4 1 1
4
原样例 2
4 5
1 2 1
1 3 2
1 4 1
2 3 1
3 4 1
4