3200. Six Degrees of Cowvin Bacon

单点时限: 1.0 sec

内存限制: 256 MB

The cows have been making movies lately, so they are ready to play a variant of the famous game “Six Degrees of Kevin Bacon”.

The game works like this: each cow is considered to be zero degrees of separation (degrees) away from herself. If two distinct cows have been in a movie together, each is considered to be one ‘degree’ away from the other. If a two cows have never worked together but have both worked with a third cow, they are considered to be two ‘degrees’ away from each other (counted as: one degree to the cow they’ve worked with and one more to the other cow). This scales to the general case.

The cows are interested in figuring out which cow has the smallest average degree of separation from all the other cows. excluding herself of course. The cows have made movies and it is guaranteed that some relationship path exists between every pair of cows.

输入格式

  • Line : Two space-separated integers: and
  • Lines ..: Each input line contains a set of two or more space-separated integers that describes the cows appearing in a single movie. The first integer is the number of cows participating in the described movie, (e.g., ); the subsequent integers tell which cows were.

输出格式

A single integer that is times the shortest mean degree of separation of any of the cows.

样例

Input
4 2
3 1 2 3
2 3 4
Output
100

提示

Cow 3 has worked with all the other cows and thus has degrees of separation: 1, 1, and 1 – a mean of 1.00 .

7 人解决,7 人已尝试。

11 份提交通过,共有 18 份提交。

9.2 EMB 奖励。

创建: 2 年,9 月前.

修改: 2 年,3 月前.

最后提交: 6 月,2 周前.

来源: USACO 2003 March Orange

题目标签