| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 2048 MB | 36 | 9 | 6 | 19.355% |
Consider an undirected graph $G$. Find the maximal number $d$ such that the lengths of all simple cycles are divisible by $d$. If there is no such number, output $0$.
The first line contains two integers $n$ and $m$: the number of vertices and edges ($1 \le n \le 5000$, $0 \le m \le 10\,000$). Each of the next $m$ lines contains three integers $a$, $b$, and $c$, which mean that there is a bidirectional edge between vertices $a$ and $b$ with length $c$ ($1 \le a, b \le n$, $1 \le c \le 10^9$). It is guaranteed that the graph doesn't contain loops or multiple edges.
Print one integer: the answer to the problem.
4 4 1 2 1 2 3 1 3 4 1 4 1 1
4
4 5 1 2 1 1 3 2 1 4 1 2 3 1 3 4 1
4