영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
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.
| Group | Point value | Constraints |
|---|---|---|
| 1 | 10 | N, ≤ 100, S ≤ 200 |
| 2 | 10 | N, ≤ 2000, S ≤ 4000 |
| 3 | 10 | M ≤ 100, S ≤ 30000 |
| 4 | 15 | L=1 |
| 5 | 55 | No 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