{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"牛群最近一直在拍电影,所以他们准备玩一个变种的著名游戏“六度分离”。\r\u003cbr\u003e\r\u003cbr\u003e游戏规则如下:每头牛被认为与自己的分离度(degrees)为零。如果两头不同的牛曾经一起出演过一部电影,那么它们之间的分离度为一。如果两头牛从未一起工作过,但都和第三头牛一起工作过,那么它们之间的分离度为二(计算方式为:一度到达它们共同工作的那头牛,再一度到达另一头牛)。这个规则可以推广到一般情况。\r\u003cbr\u003e\r\u003cbr\u003eN头(2 \u003c\u003d N \u003c\u003d 300)牛有兴趣找出哪头牛与其他所有牛的平均分离度最小,当然要排除自己。牛群一共拍了M部(1 \u003c\u003d M \u003c\u003d 10000)电影,保证每对牛之间都存在某种关系路径。\r\u003cbr\u003e"}},{"title":"输入","value":{"format":"HTML","content":"* 第1行:两个用空格分隔的整数:N 和 M\r\u003cbr\u003e\r\u003cbr\u003e* 第2行到第M+1行:每行包含两个或更多个用空格分隔的整数,描述参与一部电影的牛的情况。第一个整数是参与描述电影的牛的数量(例如Mi);随后的Mi个整数表示参与电影的牛的编号。\r\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"* 第1行:一个整数,表示任意一头牛与其他牛的最短平均分离度的100倍。\r\u003cbr\u003e"}},{"title":"示例","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\u003e4 2\r\n3 1 2 3\r\n2 3 4\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e100\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"提示","value":{"format":"HTML","content":"[牛3和其他所有牛都合作过,因此它们之间的分离度为:1, 1, 和 1 -- 平均值为1.00。]\r\u003cbr\u003e"}}]}