Hard Graph Theory > Breadth First Search/Depth First Search

Today you are a Tourist! You got chance to give tour to all over Bangladesh. Suppose Bangladesh consists of **N cities and M bidirectional roads**. Your goal is to start at some city C of your choice and visit all M roads exactly once ending this trip at C. If this is not possible, you must add the minimum number of additional roads to the initial set of roads to make this trip feasible. Note that there might be more than one road connecting the same pair of cities and that you are allowed to add roads between any pair of cities regardless of whether they already had roads connecting them or not as shown in the sample input/output. Input: ------ The first line of input gives the number of test cases, **T( ≤ 30)**. For each test case there will be Two Integer value **N (2 ≤ N ≤ 10^3)**, the number of cities and **M (1 ≤ M ≤ 10^4 )**, the number of roads respectively. The next **M** lines corresponding to the roads. Each contains two values **A** and **B** separated by one space. **A** and **B** are two distinct integers **(0 ≤ A, B < N)** indicating the end points of that road. Output: ------- For each test case, output one line containing "Case **x**: “, where **x** is the test case number, followed by the minimum number of roads needed. Sample Input ------------ 3 5 2 0 1 0 1 4 5 0 1 2 0 0 3 1 2 3 1 3 3 1 2 1 2 2 1 Sample Output ------------- Case 1: 0 Case 2: 1 Case 3: 1

Rezwanul Islam Maruf