Opinion Pool

Time limit1sMemory limit1024 MB

Summary

Given sets of voters and a fraction p, find the largest p for which some assignment with at least one opponent still satisfies every set's support quota.

Level: Hard8 of 10
Topics: Binary search, Greedy, Math, Implementation
Solved: No attempts yet

Problem

MOLOCO, a company with a global reach, is developing a new survey platform to increase user engagement.

There are $N$ people who want to vote on an issue. Each person is either in support of the issue or against it.

There are $M$ sets of people $S_1, S_2, \cdots, S_M$ , not necessarily disjoint. For these $M$ sets and a constant $p$ ( $0 \le p \le 1$ ), the following proposition holds.

For every set $S_i$ , at least $p \cdot|S_i|$ people belonging to $S_i$ are in support of the issue.

If $p = 0$ , this proposition yields no information. $p = 1$ means everyone is in support of the issue. That is, as $p$ grows, it becomes easier to determine who is in support of the issue.

Thus, if the proposition holds for a sufficiently large $p$ , we can know that everyone is in support of the issue. Find the maximum value of $p$ such that you cannot be certain everyone is in support of the issue.

Input

The first line contains two integers $N$ and $M$ , where $N$ is the number of people and $M$ is the number of sets.

The next $M$ lines describe each set.

The $i$ -th line starts with an integer $|S_i|$ , the number of elements in the set $S_i$ , followed by $|S_i|$ distinct integers $S_{i,j}$ , the elements of $S_i$ .

Output

Output the maximum value of $p$ such that you cannot be certain everyone is in support of the issue.

Your answer is considered correct if it has an absolute or relative error less than $10^{-6}$ .

Constraints

$1 \le N,M \le 200\,000$
$S_i \subseteq \{1,2,\cdots,N\}$ $(1 \le i \le M)$
$\sum_{i=1}^{M}|S_i| \le 1\,000\,000$
Everyone appears in at least one set.

Hint

In example 2, the proposition can hold for $p=0.5$ if people 1 and 3 are in support and people 2 and 4 are against.

However, if the proposition holds for $p>0.5$ , it contradicts the proposition if there is a person against the issue.

Examples3

Example 1
Input
```
3 3
1 1
1 2
1 3
```
Expected output
```
0
```
Example 2
Input
```
4 2
2 1 2
2 3 4
```
Expected output
```
0.5
```

Example 3

Input

10 7
4 8 6 10 5
4 9 5 6 1
4 4 8 1 10
4 1 5 9 3
4 6 10 5 1
4 8 3 1 10
6 5 7 6 8 1 2

Expected output

0.833333333