{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"Dhaka city is full of traffic jam and when it rains, some of the roads become unusable. So, you are asked to redesign the traffic system of the city such that if exactly one of the roads becomes unusable, it\u0027s still possible to move from any place to another using other roads.\n\nYou can assume that Dhaka is a city containing some places and bi directional roads connecting the places and it\u0027s possible to go from any place to another using the roads. There can be at most one road between two places. And of course there is no road that connects a place to itself. To be more specific there are **n** places in Dhaka city and for simplicity, assume that they are numbered from **0** to **n-1** and there are **m** roads connecting the places.\n\nYour plan is to build some new roads, but you don\u0027t want to build a road between two places where a road already exists. You want to build the roads such that if any road becomes unusable, there should be an alternate way to go from any place to another using other roads except that damaged road. As you are a programmer, you want to find the minimum number of roads that you have to build to make the traffic system as stated above."}},{"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 (\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."}},{"title":"Output","value":{"format":"MD","content":"For each case, print the case number and the minimum number of roads you have to build such that if one road goes down, it\u0027s still possible to go from any place to another."}},{"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\u003e2\n\n4 3\n1 2\n2 3\n2 0\n\n3 3\n1 2\n2 0\n0 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase 1: 2\nCase 2: 0\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":"1. Dataset is huge, use faster I/O methods.\n2. For case 1, one of the solutions is to construct two roads in (0, 1) and (1, 3)."}}]}