{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"Being an odd person, Jim always liked odd numbers. One day he was visiting his home town which consists of **n** places and **m** bidirectional roads. A road always connects two different places and there is at most one road between two places. The places are numbered from **0** to **n-1**.\n\nJim wants to find a tour which starts from a place **p** and each time it goes to a new **road** and finally at the last step it returns back to **p**. As Jim likes odd numbers, he wants the length of the tour to be odd. And the length of a tour is defined by the number of roads used in the tour.\n\n![Odd Path](CDN_BASE_URL/3c927ca102565c3a30587ca6a389928a?v\u003d1715420454)\n\nFor the city map given above, **0 - 1 - 2 - 0** is such a tour, so, **0** is one of the results, since from **0**, a tour of odd length is present. Similarly, **1 - 2 - 0 - 1** is also a valid tour. But **3 - 2 - 0 - 1 - 2 - 3** is not. since the road **2 - 3** is used twice.\n\nNow given the city map, Jim wants to find the number of places where he can start his journey for such a tour. As you are the best programmer in town, he asks you for help. Jim can use a place more than once, but a road can be visited at most once in the tour."}},{"title":"Input","value":{"format":"MD","content":"Input starts with an integer **T (\u0026le; 30)**, denoting the number of test cases.\n\nEach case starts with a blank line. The next line contains two integers: **n (3 \u0026le; n \u0026le; 10000)** and **m (0 \u0026le; m \u0026le; 20000)**. Each of the next **m** lines contains two integers **u v (0 \u0026le; u, v \u0026lt; n, u \u0026ne; v)** meaning that there is a bidirectional road between place **u** and **v**. The input follows the above constraints. And no road is reported more than once."}},{"title":"Output","value":{"format":"MD","content":"For each case, print the case number and the total number places where Jim can start his journey."}},{"title":"Sample","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\n\n6 6\n0 1\n1 2\n2 0\n3 2\n3 4\n3 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"MD","content":"Dataset is huge, user faster I/O methods."}}]}