여론 조사

전 세계를 무대로 활동하는 기업 MOLOCO는 사용자 참여를 늘리기 위해 새로운 설문 플랫폼을 개발하고 있다.

어떤 안건에 투표하려는 $N$명의 사람이 있다. 각 사람은 그 안건에 찬성하거나 반대한다.

서로 겹칠 수도 있는 $M$개의 사람 집합 $S_1, S_2, \cdots, S_M$이 있다. 이 $M$개의 집합과 상수 $p$ ($0 \le p \le 1$)에 대해 다음 명제가 성립한다.

• 모든 집합 $S_i$에 대해, $S_i$에 속한 사람 중 적어도 $p \cdot|S_i|$명이 그 안건에 찬성한다.

$p = 0$이면 이 명제에서 얻을 수 있는 정보가 없다. $p = 1$이면 모든 사람이 찬성한다는 뜻이다. 즉 $p$가 클수록 누가 찬성하는지 알아내기 쉬워진다.

따라서 충분히 큰 $p$에 대해 명제가 성립하면 모든 사람이 찬성한다는 것을 알 수 있다. 모두가 찬성한다고 확신할 수 없는 $p$의 최댓값을 구하라.

첫 번째 줄에 두 정수 $N$과 $M$이 주어진다. $N$은 사람 수, $M$은 집합 수를 나타낸다.

다음 $M$개의 줄에 각 집합의 정보가 주어진다.

$i$번째 줄은 집합 $S_i$의 원소 수 $|S_i|$로 시작하고, 이어서 $S_i$의 서로 다른 원소 $|S_i|$개 $S_{i,j}$가 주어진다.

모두가 찬성한다고 확신할 수 없는 $p$의 최댓값을 출력한다.

절대 오차 또는 상대 오차가 $10^{-6}$ 미만이면 정답으로 인정된다.

• $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$
• 모든 사람은 적어도 하나의 집합에 나타난다.

예제 2에서 1, 3번 사람이 찬성하고 2, 4번 사람이 반대하면 $p=0.5$에 대해 명제가 성립할 수 있다.

그러나 $p>0.5$에 대해 명제가 성립하면, 반대하는 사람이 존재할 경우 명제에 모순된다.