트램 노선

Stackköping의 대중교통 시스템은 $N$개의 역과 $M$개의 노선을 사용하는 트램으로 구성된다. 각 노선은 양방향으로 이동할 수 있는 역들의 순서 있는 수열로 구성된다. 트램에서 한 번의 이동은 같은 노선에 있는 두 역 사이를 이동하는 것이다. 예를 들어 노선이 역 $(3,7,5,2,1,9)$로 구성되어 있다면, $1$에서 $5$로 이동할 때 역 $1$, $2$, $5$을 지나간다.

Stackköping에서 흔히 발생하는 건강 문제는 사람들이 걷는 대신 트램을 타고 짧은 거리를 이동한다는 것이다. 이에 대응하기 위해 지방 자치 단체는 이동 요금이 낭비량에 비례하는 새로운 결제 시스템으로 전환하기로 했다. 한 번의 이동에서 발생하는 낭비량은 트램이 지나가지 않는 해당 노선의 역 수로 정의한다. 위 예제에서 역 $3,7,$와 $9$을 지나가지 않으므로 낭비량은 $3$이다.

여러 번의 이동을 통해 역 $1$에서 역 $N$로 가려고 한다. 가능한 총 낭비량의 최솟값은 얼마인가? 역 $1$에서 모든 역에 도달할 수 있음이 보장된다.

점수

당신의 풀이는 여러 테스트 케이스 그룹에 대해 테스트된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한

$1$ |$10$| $N,\le 100, S \le 200$

$2$ |$10$| $N,\le 2000, S \le 4000$

$3$ |$10$| $M \le 100, S \le 30000$

$4$ |$15$| $L=1$

$5$ |$55$| 추가 제한 없음.

입력의 첫 번째 줄에는 트램망의 역 수와 노선 수를 나타내는 두 정수 $N$와 $L$가 주어진다 ($2 \leq N,L \leq 10^5$).

이어지는 $L$개의 줄은 각각 트램 노선 하나를 설명한다. 각 줄은 정수 $M$로 시작하고 그 뒤에 $1$ 이상 $N$ 이하인 $M$개의 정수가 주어진다 ($2 \le M \le N$). 이들은 트램 노선에 있는 역의 수와 그 역들을 나타낸다. 이 $M$개의 정수는 모두 서로 다르다.

모든 트램 노선에 대한 $M$의 합을 $S$라고 하자. $S \leq 3 \cdot 10^5$임이 보장된다.

역 $1$에서 역 $N$로 이동하는 데 필요한 가능한 총 낭비량의 최솟값을 정수로 출력한다.

첫 번째 예제에서는 먼저 첫 번째 노선을 이용해 $1$에서 $2$로 이동한다. 그런 다음 두 번째 노선을 이용해 $2$에서 $6$로 이동할 수 있다. 각 이동의 낭비량은 $1$과 $2$이므로 답은 $3$이다.

두 번째 예제에서는 먼저 $1$에서 $4$로 이동할 수 있으며, 낭비량은 $1$이다. 그다음 $4$에서 $5$로 이동하며, 노선상의 모든 역을 방문하므로 낭비량은 $0$이다.