K-Divisible Graph

Time limit2sMemory limit1024 MB

Summary

Given a weighted undirected graph and K, decide whether every closed walk has total weight divisible by K.

Level: Medium6 of 10
Topics: Graph, Union-find, Math
Solved: No attempts yet

Problem

A weighted undirected graph is called a $K$ -divisible graph if, for every closed walk $P$ in the graph, the sum of the edge weights along $P$ is always a multiple of $K$ . If an edge is used several times, its weight is added to the sum once for each use.

Given a weighted undirected graph $G$ and a positive integer $K$ , determine whether $G$ is a $K$ -divisible graph.

Input

The first line contains the number of vertices $N$ , the number of edges $M$ , and the positive integer $K$ , separated by spaces. ( $1 \le N \le 300\,000$ , $0 \le M \le 500\,000$ , $1 \le K \le 10^9$ )

Each of the next $M$ lines contains three integers $v_i$ , $w_i$ , and $x_i$ , separated by spaces. This describes an undirected edge with weight $x_i$ between vertex $v_i$ and vertex $w_i$ . ( $1 \le v_i, w_i \le N$ , $0 \le x_i \le 10^9$ )

There can be several edges between the same pair of vertices, and an edge may connect a vertex to itself. The graph may not be connected.

Output

If the given graph is a $K$ -divisible graph, print Yes. Otherwise, print No.

Hint

A closed walk is a walk that starts and ends at the same vertex. It may visit the same vertices and edges several times.

Examples2

Example 1
Input
```
3 3 6
1 2 3
2 3 6
3 1 9
```
Expected output
```
Yes
```
Example 2
Input
```
4 4 7
1 2 3
2 3 2
3 4 3
4 2 2
```
Expected output
```
No
```