Many Many Cycles

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

요약

가중치가 있는 무방향 그래프에서 모든 단순 사이클의 길이를 나누는 가장 큰 정수 d를 구합니다. 그런 d가 없으면 0을 출력합니다.

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

문제

무방향 그래프 $G$ 가 주어진다. 모든 단순 사이클의 길이가 $d$ 로 나누어떨어지는 최대의 $d$ 를 구하라. 그러한 $d$ 가 없으면 $0$ 을 출력한다.

입력

첫 번째 줄에 정점의 수 $n$ 과 간선의 수 $m$ 이 주어진다 ( $1 \le n \le 5000$ , $0 \le m \le 10\,000$ ). 다음 $m$ 개의 줄에는 세 정수 $a$ , $b$ , $c$ 가 주어지며, 이는 정점 $a$ 와 $b$ 사이에 길이가 $c$ 인 양방향 간선이 있다는 뜻이다 ( $1 \le a, b \le n$ , $1 \le c \le 10^9$ ). 그래프에는 자기 루프나 중복 간선이 없다.

출력

답을 나타내는 정수 하나를 출력한다.

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