루미 알고리즘

#1516플래티넘Tramway

PO 2021 훈련 캠프코딩출제 David Wärn, Fredrik Ekholm영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

The public transportation system in Stackköping consists of a tramway using N stations and M lines. Each line consists of an ordered sequence of stations where it is possible to travel in both directions. A journey on the tramway is a movement between two stations on the same line. For example, if the line consists of the stations (3,7,5,2,1,9), a journey from 1 to 5 will pass through stations 1, 2, and 5.

A common health issue in Stackköping is that people take short trips on the tramway instead of walking. To counteract this, the municipality has decided to switch to a new payment system where the price for a journey is proportional to the waste. The waste of a journey is defined as the number of stations on the line that the tramway does not pass through. In the example above, the waste is 3, because stations 3,7, and 9 are not passed through.

You want to travel from station 1 to station N through a sequence of journeys. What is the minimum possible total waste? It is guaranteed that it is possible to reach all stations from station 1.

Input

The first line of input contains two integers N and L (2 ≤ N,L ≤ 10^5), the number of stations and the number of lines in the tramway network.

The following L lines each describe a tramway line. Each of these lines begin with an integer M (2 ≤ M ≤ N) followed by M integers between 1 and N, the number of stations on the tramway line and its stations. These M integers are all distinct.

Let S be the sum of M over all tramway lines. It is guaranteed that S ≤ 3 · 10^5.

Output

Print an integer: the smallest possible total waste required to travel from station 1 to station N.

Points

Your solution will be tested on several test case groups. To get the points for a group, it must pass all the test cases in the group.

GroupPoint valueConstraints
110N, ≤ 100, S ≤ 200
210N, ≤ 2000, S ≤ 4000
310M ≤ 100, S ≤ 30000
415L=1
555No further constraints.

Explanation of Samples

In the first sample, we first travel from 1 to 2 using the first line. We can then travel from 2 to 6 using the second line. The total waste for the trips is 1 and 2, therefore the answer is 3.

In the second sample we can start by travelling from 1 to 4, with waste 1. Afterwards, we travel from 4 to 5, which has a waste of 0 as all stations along the line are visited.

예제

예제 1

입력
6 2
3 1 2 3
4 4 2 6 5
출력
3

예제 2

입력
5 1
5 5 1 2 3 4
출력
1

출처 표기

출처: Programmeringsolympiaden 2021년 훈련 캠프 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.