時間制限 : sec, メモリ制限 : KB
Japanese

F: Clique Drawing

問題文

$M$ 回操作を行って $N$ 頂点のグラフを作ります。 初め、$N$ 頂点のどの頂点間にも辺は存在しません。 $i$ 番目の操作では、頂点集合 $\{ v_{i, 1}, v_{i, 2}, ... , v_{i, K_i} \}$ の全ての $2$ 頂点間に辺を張ります。ただし、以前の操作によって既に辺が貼られている頂点間には張りません。 また、どの頂点も $M$ 回の操作の内高々 $2$ 回の操作にしか現れません。 これらの操作によって出来たグラフ上の、最大独立集合の大きさを求めてください。

無向グラフ $G = (V, E)$ の独立集合 $U$ とは、$U \subseteq V$ なる頂点の部分集合であって、全ての $u, v \in U$ について、$(u, v) \notin E$ を満たすものを指します。 最大独立集合とは、このような独立集合の内、最も大きいものを指します。

制約

  • 入力は全て整数
  • $1 \leq N \leq 10^5$
  • $1 \leq M \leq 300$
  • $2 \leq K_i \leq N$ ($1 \leq i \leq M$)
  • $1 \leq v_{i, j} \leq N$ ($1 \leq i \leq M, 1 \leq j \leq K_i$)
  • $\{ v_{i, 1}, v_{i, 2}, ... , v_{i, K_i} \}$ の中に重複した値は存在しない ($1 \leq i \leq M$)
  • 全ての頂点は最大でも2回の操作にしか含まれない

入力

入力は以下の形式で標準入力から与えられます。

$N$ $M$
$K_1$ $v_{1, 1}$ $\ldots$ $v_{1, K_1}$
$\vdots$
$K_M$ $v_{M, 1}$ $\ldots$ $v_{M, K_M}$

出力

答えを一行で出力してください。

入出力例

入力例1

2 1
2 1 2

出力例1

1

1回の操作の後、2頂点からなる道が出来ます。 したがって、最大独立集合の大きさは1です。

入力例2

4 1
3 1 2 3

出力例2

2

入力例3

6 3
3 2 3 5
3 3 4 6
3 1 2 4

出力例3

3