Inspector’s Dilemma

Input: Standard Input

Output: Standard Output

In a country, there are a number of cities. Each pair of city is connected by a highway, bi-directional of course. A road-inspector’s task is to travel through the highways (in either direction) and to check if everything is in order. Now, a road-inspector has a list of highways he must inspect. However, it might not be possible for him to travel through all the highways on his list without using other highways. He needs a constant amount of time to traverse any single highway. As you can understand, the inspector is a busy fellow does not want to waste his precious time. He needs to know the minimum possible time to complete his task. He has the liberty to start from and end with any city he likes. Please help him out.

Input

The input file has several test cases. First line of each case has three integers: V (1 ≤ V ≤ 1000), the number of cities, E (0 ≤ E ≤ V * (V-1) / 2), the number of highways the inspector needs to check and T (1 ≤ T ≤ 10), time needed to pass a single highway. Each of the next E lines contains two integers a and b (1 ≤ a,b ≤ V, a!=b) meaning the inspector has to check the highway between cities a and b. The input is terminated by a case with V=E=T=0. This case should not be processed.

Output

For each test case, print the serial of output followed by the minimum possible time the inspector needs to inspect all the highways on his list. Look at the output for sample input for details.

Sample Input Output for Sample Input

5 3 1

1 2

1 3

4 5

4 4 1

1 2

1 4

2 3

3 4

0 0 0

Case 1: 4

Case 2: 4

Problem setter: Mohammad Mahmudur Rahman,

Special Thanks: Abdullah al Mahmud & Syed Monowar Hossain