영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
Problem
Current urban planning is flawed. Many busses and trams are needed to support a public transportation network. What if we were to build an entire city along a line? Then, the entire city's transportation needs could be met with a few high-speed trains. With this brilliant idea, a city with N train stations was built, each indexed between 1 and N. For every train station i with 1 ≤ i < N, there is a train line to train station i+1, which takes 1 minute. Each line can be taken in both directions.
After a couple of years, it turns out that the shape of the city might not be optimal. Thankfully, due to the prosperity of the city, you have developed a teleporter. You are going to install the first teleporter and want to maximize its impact. If you install the teleporter between train stations i and j, you can teleport between the train stations in both directions. Teleporting takes one minute. There are K people in the city. Person i lives in train station s_i and works in train station t_i. Let dist(s,t) be the number of minutes that the shortest possible path between s and t takes, which may or may not use the teleporter.
If you install the teleporter optimally, what is the minimum possible value of
∑_{i=1}^K dist(s_i, t_i)
Input
The first line contains two integers N and K (1 ≤ N ≤ 10^9, 1 ≤ K ≤ 10,000), the number of train stations and the number of people.
The following K lines each contain two integers s and t (1 ≤ s,t ≤ N), meaning that there is a person who lives at train station s and works at train station t. It is not guaranteed that all pairs (s,t) are unique.
Output
Print an integer: the smallest total travel time if the teleporter is installed optimally.
Scoring
Your solution will be tested on a set of test groups. To earn points for a group, you must pass all test cases in that group.
| Group | Points | Constraints |
|---|---|---|
| 1 | 7 | N, K ≤ 50 |
| 2 | 14 | N, K ≤ 500 |
| 3 | 27 | N, K ≤ 2000 |
| 4 | 13 | N ≤ 2 · 10^5, K ≤ 500 |
| 5 | 18 | N ≤ 2 · 10^5, K ≤ 2000 |
| 6 | 21 | No additional constraints. |
Explanation of Samples
In sample 1, it is optimal to build the teleporter such that the single inhabitant can go work in one minute.
In sample 2, one optimal solution is to build the teleporter between train stations 2 and 9. In the drawing, every person's home is connected with their place of work, and the optimal teleporter is drawn as a dotted line.
(그림은 원문 저장소에서 볼 수 있습니다)
The person who lives at train station 1 takes the path 1 → 2 → 9 → 10, the person at 2 takes 2 → 9, and the person at 5 takes 5 → 6 → 7. In total, this takes 3+1+2=6 minutes, which is optimal.
In sample 3, one optimal solution is to build a teleporter between train stations 2 and 9.
예제
예제 1
5 1 2 4
1
예제 2
10 3 1 10 2 9 5 7
6
예제 3
10 5 1 5 3 4 5 7 9 2 8 8
8