{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"有N个牧场(牧场编号1~N),Bessie 要从一个牧场到另一个牧场,要求至少要有2条独立的路可以走。现已有M条路,求至少要新建多少条路,使得任何两个牧场之间至少有两条独立的路。两条独立的路是指:没有公共边的路,但可以经过同一个中间顶点。"}},{"title":"Input","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n 第1行:给出N,M,分别表示总共有N个牧场,和M条边。1\u003c\u003dN\u003c\u003d5000,N-1\u003c\u003dM\u003c\u003d10000。\n \u003cbr\u003e \n \u003cbr\u003e\n 第2~M+1行:每行给出两个数,表示两个牧场间有一条边。\n \u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n 输出需要新建道路的数量。\n \u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e7 7\n1 2\n2 3\n3 4\n2 5\n4 5\n5 6\n5 7\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e2\u003c/pre\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003e\n Explanation of the sample: \n \u003cbr\u003e \n \u003cbr\u003eOne visualization of the paths is: \n \u003cbr\u003e\n \u003cpre\u003e 1 2 3\u003cbr\u003e +---+---+ \u003cbr\u003e | |\u003cbr\u003e | |\u003cbr\u003e 6 +---+---+ 4\u003cbr\u003e / 5\u003cbr\u003e / \u003cbr\u003e / \u003cbr\u003e 7 +\u003c/pre\u003eBuilding new paths from 1 to 6 and from 4 to 7 satisfies the conditions. \n \u003cbr\u003e\n \u003cpre\u003e 1 2 3\u003cbr\u003e +---+---+ \u003cbr\u003e : | |\u003cbr\u003e : | |\u003cbr\u003e 6 +---+---+ 4\u003cbr\u003e / 5 :\u003cbr\u003e / :\u003cbr\u003e / :\u003cbr\u003e 7 + - - - - \u003c/pre\u003eCheck some of the routes: \n \u003cbr\u003e\n \u003cspan lang\u003d\"en-us\"\u003e1 – 2: 1 –\u0026gt; 2 and 1 –\u0026gt; 6 –\u0026gt; 5 –\u0026gt; 2 \u003cbr\u003e1 – 4: 1 –\u0026gt; 2 –\u0026gt; 3 –\u0026gt; 4 and 1 –\u0026gt; 6 –\u0026gt; 5 –\u0026gt; 4 \u003cbr\u003e3 – 7: 3 –\u0026gt; 4 –\u0026gt; 7 and 3 –\u0026gt; 2 –\u0026gt; 5 –\u0026gt; 7\u003c/span\u003e \n \u003cbr\u003eEvery pair of fields is, in fact, connected by two routes. \n \u003cbr\u003e \n \u003cbr\u003eIt\u0027s possible that adding some other path will also solve the problem (like one from 6 to 7). Adding two paths, however, is the minimum.\n \u003c/div\u003e"}}]}