Minimum Total Weight for Edge Condition

You are given an undirected graph with N vertices and M edges along with a weight value W. For each edge in the graph, the following condition must be satisfied:

If an edge connects vertices u and v, then the sum of the weights assigned to these two vertices must be exactly 2W.

In other words, if we denote the weight assigned to vertex i by a_i, then for every edge \((u,v)\) the following must hold: \[ a_u + a_v = 2W \]

Your task is to choose weights for the vertices (each vertex can only be assigned a weight of either 0 or W) so that the above condition holds for every edge and the total sum of weights is minimized. After some analysis, it turns out that if there is at least one edge in the graph, the optimal strategy is to assign the weight W to exactly two vertices, regardless of the graph structure, thus yielding a minimum total weight of \(2W\). If there are no edges at all, then no vertex needs to be assigned a weight and the answer is 0.

Note: Although the graph details are provided, the solution does not depend on the structure of the graph. Simply check if M is 0. If yes, output 0; otherwise, output \(2W\).

inputFormat

The input is read from standard input and has the following format:

N M W
u1 v1
u2 v2
... 
 uM vM

The first line contains three integers N (the number of vertices), M (the number of edges), and W (the weight value). Each of the following M lines contains two space-separated integers representing an edge between two vertices.

outputFormat

Output a single integer — the minimum total sum of weights needed such that for every edge \((u,v)\), \(a_u + a_v = 2W\).

## sample

4 4 5
1 2
2 3
3 4
4 1

10