{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e给你一棵树$$$n$$$个结点$$$m$$$条边,树的每个结点都有一个权值.\n\u003cp\u003e请你删掉一条边,使得分成的两棵树权值之和相差最小\u003cbr\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\n\u003cp\u003e多组数据读入。\n\u003cp\u003e每组数据先给出两个整数 \u003ci\u003eN\u003c/i\u003e 和 \u003ci\u003eM\u003c/i\u003e, ($$$1 ≤N ≤ 100000$$$, $$$1 ≤ M ≤ 100000$$$),代表这棵树的结点数目和边的数目。其中结点编号为$$$1$$$~$$$N$$$。\n\u003cp\u003e接着给出 \u003ci\u003eN\u003c/i\u003e 个整数代表每个点的权值(每个数不超过$$$100000000$$$)\n\u003cp\u003e接下来\u003ci\u003eM\u003c/i\u003e 行,每行两个整数\u003ci\u003es\u003c/i\u003e, \u003ci\u003et\u003c/i\u003e, 代表两点之间有一条边.\u003c/p\u003e\n\u003cp\u003e\u003ci\u003eN\u003c/i\u003e \u003d 0, \u003ci\u003eM\u003c/i\u003e \u003d 0 代表输入结束.\u003c/p\u003e\u003c/span\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e输出一行:Case $$$x: y$$$\n\u003cp\u003e$$$x$$$代表第$$$x$$$组数据,$$$y$$$代表权值最小差值"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e7 6\n1 1 1 1 1 1 1\n1 2\n2 7\n3 7\n4 6\n6 2\n5 7\n0 0\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003eCase 1: 1\u003c/pre\u003e"}}]}