{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eGiven an undirected graph, in which two vertices can be connected by multiple edges, what is the size of the minimum cut of the graph? i.e. how many edges must be removed at least to disconnect the graph into two subgraphs?\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cspan lang\u003d\"en-us\"\u003e\u003cp\u003eInput contains multiple test cases. Each test case starts with two integers \u003ci\u003eN\u003c/i\u003e and \u003ci\u003eM\u003c/i\u003e (2 ≤ \u003ci\u003eN\u003c/i\u003e ≤ 500, 0 ≤ \u003ci\u003eM\u003c/i\u003e ≤ \u003ci\u003eN\u003c/i\u003e × (\u003ci\u003eN\u003c/i\u003e − 1) ⁄ 2) in one line, where \u003ci\u003eN\u003c/i\u003e is the number of vertices. Following are \u003ci\u003eM\u003c/i\u003e lines, each line contains \u003ci\u003eM\u003c/i\u003e integers \u003ci\u003eA\u003c/i\u003e, \u003ci\u003eB\u003c/i\u003e and \u003ci\u003eC\u003c/i\u003e (0 ≤ \u003ci\u003eA\u003c/i\u003e, \u003ci\u003eB\u003c/i\u003e \u0026lt; \u003ci\u003eN\u003c/i\u003e, \u003ci\u003eA\u003c/i\u003e ≠ \u003ci\u003eB\u003c/i\u003e, \u003ci\u003eC\u003c/i\u003e \u0026gt; 0), meaning that there \u003ci\u003eC\u003c/i\u003e edges connecting vertices \u003ci\u003eA\u003c/i\u003e and \u003ci\u003eB\u003c/i\u003e.\u003c/p\u003e\u003c/span\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eThere is only one line for each test case, which contains the size of the minimum cut of the graph. If the graph is disconnected, print 0.\u003c/p\u003e"}},{"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\u003e3 3\r\n0 1 1\r\n1 2 1\r\n2 0 1\r\n4 3\r\n0 1 1\r\n1 2 1\r\n2 3 1\r\n8 14\r\n0 1 1\r\n0 2 1\r\n0 3 1\r\n1 2 1\r\n1 3 1\r\n2 3 1\r\n4 5 1\r\n4 6 1\r\n4 7 1\r\n5 6 1\r\n5 7 1\r\n6 7 1\r\n4 0 1\r\n7 3 1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\r\n1\r\n2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}