Many Many Cycles

시간 제한2초메모리 제한2048 MB

요약

가중 무향 그래프에서 모든 단순 사이클 길이의 공통 약수 중 가장 큰 d를 구하고, 없으면 0을 출력한다.

난이도: 보통10점 중 7점
유형: 그래프, 정수론, 유니온 파인드, DFS
정답자: 아직 제출이 없습니다

문제

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.

예제2

예제 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
```