요정들

사악한 용 비톨이 요정들의 나라를 침략해 주민들을 노예로 붙잡았다. 그는 $n$명의 요정에게 각자 서로 다른 작업 자리를 하나씩 배정한 뒤, 훔친 보물 더미 위에 드러누워 게으르게 그들의 고된 노동을 감시한다.

비톨은 지독히 나태한 용이라 모든 부하를 동시에 지켜보지는 않는다. 대신 언제나 특정한 자리 무리에서 일하는 요정들만 주의 깊게 바라본다. 그 동안 그가 보고 있지 않은 요정들은 서로 만나 자리를 자유롭게 맞바꿀 수 있다(비톨은 어떤 요정이 어느 자리에서 일했는지 기억하지 못한다). 매시간 용은 고개를 돌려 다른 요정 무리를 관찰하기 시작한다.

$1$번 자리를 배정받은 요정 바이타질은 동료들을 규합해 비톨에게 맞서고자 한다. 그러려면 먼저 $n$번 자리를 배정받은 원로 요정 바이토미르를 만나야 한다. 따라서 바이타질에게는 과제가 하나 있다. 다른 요정들과 적절히 자리를 맞바꿔서, 자신이 지금 서 있는 자리와 $n$번 자리가 모두 용에게 관찰되지 않는 상황을 최대한 빨리 만들어야 한다.

너의 임무는 이 만남이 가장 이르면 언제 이루어질 수 있는지 알아내는 것이다. 다행히 $m$시간이 지나면 비톨이 잠들고, 그때부터는 모든 요정이 자유롭게 소통할 수 있다는 사실이 알려져 있다.

첫 번째 줄에는 두 정수 $n$과 $m$ ($1 \le n, m \le 1\,000\,000$)이 주어진다. 각각 요정의 수와 비톨이 잠들기까지 남은 시간(시간 단위)을 뜻한다. 다음 $m$개의 줄에는 각 시간마다 용이 관찰하는 자리 무리의 설명이 한 줄에 하나씩 주어진다. $i$번째 무리의 설명은 관찰되는 자리의 개수를 뜻하는 정수 $k_i$ ($1 \le k_i \le n$)와, 관찰되는 자리 번호를 뜻하는 $\{1, \dots, n\}$의 오름차순 정수 $k_i$개로 이루어진다. 한 줄의 모든 수는 공백 하나로 구분된다.

$k_1 + k_2 + \dots + k_m \le 2\,000\,000$이라고 가정해도 된다.

표준 출력의 첫 번째이자 유일한 줄에 $\{0, \dots, m\}$에 속하는 정수 하나, 즉 바이타질이 바이토미르에게 도달할 수 있는 가장 이른 시간 수를 출력하여라.

예시 설명

첫 번째 예시에서 바이타질은 여정의 첫 시간 동안 $1$번 자리를 떠날 수 없다. 그 자리가 용에게 관찰되고 있기 때문이다. 두 번째 시간에는 $4$번 자리의 요정과 자리를 맞바꿀 수 있다. 덕분에 세 번째 시간이 시작될 때 비로소 비톨이 $1$, $2$, $3$번 자리로 고개를 돌리고, 바이타질은 바이토미르를 만날 수 있게 된다.

두 번째 예시에서는 첫 시간에 용이 바이타질과 바이토미르의 자리를 보고 있지 않으므로 곧바로 만남이 이루어질 수 있다.

세 번째 예시에서는 비톨이 잠든 뒤에야 만남이 가능하다.