{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"content\"\u003e\r\n\t\u003cimg border\u003d\"0\" src\u003d\"http://www.lydsy.com:808/JudgeOnline/images/1912_1.jpg\" /\u003e\u003ca href\u003d\"http://www.apio.olympiad.org/2010/apio2010-en.pdf\"\u003ehttp://www.apio.olympiad.org/2010/apio2010-en.pdf\u003c/a\u003e\u0026nbsp;see the problem \u0026quot;Patrol\u0026quot;\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"content\"\u003e\r\n\t\u003cspan data-scayt_word\u003d\"第一行包含两个整数\" data-scaytid\u003d\"13\"\u003e第一行包含两个整数\u003c/span\u003e n, K(1 \u0026le; K \u0026le; 2)\u003cspan data-scayt_word\u003d\"。接下来\" data-scaytid\u003d\"14\"\u003e。接下来\u003c/span\u003e n \u0026ndash; \u003cspan data-scayt_word\u003d\"1行,每行两个整数\" data-scaytid\u003d\"15\"\u003e1行,每行两个整数\u003c/span\u003e a, \u003cspan data-scayt_word\u003d\"b,\" data-scaytid\u003d\"16\"\u003eb,\u003c/span\u003e \u003cspan data-scayt_word\u003d\"表示村庄a与b之间有一条道路\" data-scaytid\u003d\"17\"\u003e表示村庄a与b之间有一条道路\u003c/span\u003e(1 \u0026le; a, b \u0026le; n)。\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"content\"\u003e\r\n\t\u003cspan data-scayt_word\u003d\"输出一个整数,表示新建了K\" data-scaytid\u003d\"9\"\u003e输出一个整数,表示新建了K\u003c/span\u003e \u003cspan data-scayt_word\u003d\"条道路后能达到的最小巡逻距离。\" data-scaytid\u003d\"10\"\u003e条道路后能达到的最小巡逻距离。\u003c/span\u003e\u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"content\"\u003e\r\n\t\u003cpre class\u003d\"sampledata\"\u003e\r\n\t8 1 \r\n1 2 \r\n3 1 \r\n3 4 \r\n5 3 \r\n7 5 \r\n8 5 \r\n5 6 \u003c/pre\u003e\r\n\u003c/div\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"content\"\u003e\r\n\t\u003cpre class\u003d\"sampledata\"\u003e\r\n\t11\u003c/pre\u003e\r\n\u003c/div\u003e"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cdiv class\u003d\"content\"\u003e\r\n\t\u003cp\u003e\r\n\t\t10%\u003cspan data-scayt_word\u003d\"的数据中,n\" data-scaytid\u003d\"1\"\u003e的数据中,n\u003c/span\u003e \u0026le; 1000, K \u003d \u003cspan data-scayt_word\u003d\"1;\" data-scaytid\u003d\"2\"\u003e1;\u003c/span\u003e\u003cbr /\u003e\r\n\t\t30%\u003cspan data-scayt_word\u003d\"的数据中,K\" data-scaytid\u003d\"4\"\u003e的数据中,K\u003c/span\u003e \u003d \u003cspan data-scayt_word\u003d\"1;\" data-scaytid\u003d\"3\"\u003e1;\u003c/span\u003e\u003cbr /\u003e\r\n\t\t80%\u003cspan data-scayt_word\u003d\"的数据中,每个村庄相邻的村庄数不超过\" data-scaytid\u003d\"5\"\u003e的数据中,每个村庄相邻的村庄数不超过\u003c/span\u003e \u003cspan data-scayt_word\u003d\"25;\" data-scaytid\u003d\"7\"\u003e25;\u003c/span\u003e\u003cbr /\u003e\r\n\t\t90%\u003cspan data-scayt_word\u003d\"的数据中,每个村庄相邻的村庄数不超过\" data-scaytid\u003d\"6\"\u003e的数据中,每个村庄相邻的村庄数不超过\u003c/span\u003e \u003cspan data-scayt_word\u003d\"150;\" data-scaytid\u003d\"8\"\u003e150;\u003c/span\u003e\u003cbr /\u003e\r\n\t\t100%\u003cspan data-scayt_word\u003d\"的数据中,3\" data-scaytid\u003d\"11\"\u003e的数据中,3\u003c/span\u003e \u0026le; n \u0026le; 100,000, 1 \u0026le; K \u0026le; \u003cspan data-scayt_word\u003d\"2。\" data-scaytid\u003d\"12\"\u003e2。\u003c/span\u003e\u003c/p\u003e\r\n\u003c/div\u003e"}}]}