Problem #3200 - ECNU Online Judge

单点时限: 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 $N$ $(2 \leq N \leq 300)$ 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 $M$ $(1 \leq M \leq 10000)$ movies and it is guaranteed that some relationship path exists between every pair of cows.

输入格式

Line $1$ : Two space-separated integers: $N$ and $M$
Lines $2$ .. $M + 1$ : 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., $M_{i}$ ); the subsequent $M_{i}$ integers tell which cows were.

输出格式

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

样例

Input

4 2
3 1 2 3
2 3 4

Output

提示

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

10 人解决，10 人已尝试。

14 份提交通过，共有 40 份提交。

5.1 EMB 奖励。

创建: 7 年，11 月前.

修改: 7 年，5 月前.

最后提交: 4 周前.

来源: USACO 2003 March Orange

bfs shortest paths

3200. Six Degrees of Cowvin Bacon

输入格式

输出格式

样例

提示

服务

开源

关于我们