$K$ 분 그래프

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

요약

무방향 가중치 그래프의 모든 닫힌 보행에서 간선 가중치 합이 항상 K의 배수인지 판별한다.

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

문제

어떤 무방향 가중치 그래프가 $K$ 분 그래프라는 건, 그래프의 모든 닫힌 보행 $P$ 에 대해, $P$ 의 간선 가중치 합이 항상 $K$ 의 배수인 그래프를 의미한다. 이때 하나의 간선을 여러 번 사용했다면 간선 가중치 합에도 여러 번 더해진다.

무방향 가중치 그래프 $G$ 와 양의 정수 $K$ 가 주어질 때, $G$ 가 $K$ 분 그래프인지 판별해 보자.

입력

첫째 줄에는 그래프 $G$ 의 정점 개수 $N$ 과 간선 개수 $M$ , 그리고 문제에서 설명한 양의 정수 $K$ 가 공백으로 구분되어 주어진다. $(1\le N\le 300\\, 000;$ $0\le M\le 500\\, 000;$ $1\le K\le 10^9)$

이후 $M$ 개의 줄에 걸쳐 3개의 정수 $v\_i,w\_i,x\_i$ 가 공백으로 구분되어 주어진다. 이는 $v\_i$ 번 정점과 $w\_i$ 번 정점을 연결하는 가중치 $x\_i$ 의 양방향 간선을 의미한다. $(1\le v\_i,w\_i\le N;$ $0\le x\_i\le 10^9)$

두 정점을 잇는 간선이 여러 개일 수 있으며, 같은 정점을 잇는 간선이 존재할 수 있다. 또한, 주어지는 그래프가 연결되어 있지 않을 수도 있다.

출력

주어진 그래프가 $K$ 분 그래프라면 Yes를, 아니면 No를 출력한다.

힌트

닫힌 보행이란 시작점과 끝점이 같으며, 같은 정점과 간선을 여러 번 방문할 수 있는 경로를 말한다.

예제2

예제 1
입력
```
3 3 6
1 2 3
2 3 6
3 1 9
```
예상 출력
```
Yes
```
예제 2
입력
```
4 4 7
1 2 3
2 3 2
3 4 3
4 2 2
```
예상 출력
```
No
```