**7 人解决**，7 人已尝试。

**11 份提交通过**，共有 18 份提交。

**9.2** EMB 奖励。

**单点时限: **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

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 奖励。

题目标签