루미 알고리즘

#1641다이아The Line

PO 2026 훈련 캠프코딩출제 Joshua Andersson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

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

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.

GroupPointsConstraints
17N, K ≤ 50
214N, K ≤ 500
327N, K ≤ 2000
413N ≤ 2 · 10^5, K ≤ 500
518N ≤ 2 · 10^5, K ≤ 2000
621No 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

출처 표기

출처: Programmeringsolympiaden 2026년 훈련 캠프 · 원문 페이지 · 이용 조건 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). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.