상자 내리기

한 아이가 이사를 했다. 이사하기 전에 아이는 책을 모두 번호가 붙은 상자에 나눠 담았고, 어떤 책이 어느 상자에 들어 있는지 적은 목록을 만들어 1번 상자에 넣어 두었다.

새 방에 들어와 보니 부모님이 상자를 여러 더미로 쌓아 한 줄로 나란히 놓아 두었다. 각 더미는 바로 옆 더미와 맞닿아 있다.

아이는 순서를 따지는 성격이라 다른 상자를 열기 전에 먼저 그 목록을 되찾으려 한다. 그런데 손이 서툴러서, 상자 하나를 꺼내려면 그 상자가 더미의 맨 위에 있어야 하고 왼쪽과 오른쪽 중 적어도 한쪽이 비어 있어야 한다. 어느 쪽이 비어 있는지는 상관없다.

왼쪽에서 $i$번째 더미의 바닥에서 $h$번째 자리에 놓인 상자를 생각해 보자. $i-1$번째 더미에 그 순간 상자가 $h$개 이상 쌓여 있으면 왼쪽이 막혀 있고, 그렇지 않으면 왼쪽이 비어 있다. 오른쪽은 $i+1$번째 더미를 같은 방식으로 본다. 맨 왼쪽 더미의 왼쪽과 맨 오른쪽 더미의 오른쪽에는 아무것도 없으므로 그 쪽은 항상 비어 있다.

방이 넓어서 꺼낸 상자는 부모님이 쌓아 둔 더미를 건드리지 않고 다른 곳에 내려놓는다.

더미에 쌓인 상자의 위치가 주어질 때, 1번 상자를 꺼내려면 1번 상자 외에 최소 몇 개의 상자를 꺼내야 하는지 구하라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 상자의 개수 $N$과 더미의 개수 $P$가 주어진다 ($1 \le P \le N \le 1000$). 상자에는 1부터 $N$까지 번호가 붙어 있다.

이어지는 $P$개의 줄은 왼쪽부터 순서대로 각 더미를 설명한다. 그중 $i$번째 줄에는 $i$번 더미에 쌓인 상자의 개수 $Q_i$가 먼저 주어지고, 공백 하나를 둔 다음 $Q_i$개의 상자 번호가 공백으로 구분되어 주어진다. 번호는 더미의 바닥부터 맨 위까지 순서대로 나열된다.

모든 더미에는 상자가 적어도 하나 있고, 모든 상자는 입력 전체에서 정확히 한 번씩 나타난다. 상자의 모양과 크기는 모두 같다.

$N$과 $P$가 모두 0인 줄이 입력의 끝을 나타낸다. 이 줄은 테스트 케이스가 아니다.

각 테스트 케이스마다 한 줄에 정수 하나를 출력한다. 1번 상자를 꺼내기 위해 1번 상자 외에 꺼내야 하는 상자의 최소 개수이다.