User's AC Ratio

90.9% (10/11)

Submission's AC Ratio

58.5% (24/41)

Description

給你 $n$ 個點及 $m$ 條邊的圖，並且點的編號為 $1$ 到 $n$

當滿足以下條件，稱圖為和諧的圖：
對於任意 $(l, m, r)$ 其中 $l < m < r$，若點 $l$ 到點 $r$ 之間存在一條路徑，則點 $l$ 到點 $m$ 也必須存在一條路徑

換句話說，若點 $l$ 可通過邊走到點 $r$，那麼點 $l$ 同時要能走到點 $l+1, l+2, l+3, \cdots r-1$

請問最少要加多少條邊才能使圖變為和諧的圖？

Input Format

一開始給定數 $n, m$ 表示點的數量以及邊的數量 ($3 \le n \le 2\cdot 10^ 5$ 及 $1 \le m \le 2\cdot 10^ 5$)
接著有 $m$ 列，每列有兩個數 $u, v$ 表示點 $u$ 與點 $v$ 之間有邊 ($1 \le u, v \le n, u \not= v$)

Output Format

輸出最少要加的邊數量，使圖變為和諧的圖。

Sample Input 1

3 1
1 3

Sample Output 1

Sample Input 2

500 5
100 300
200 400
420 440
430 450
435 460

Sample Output 2

335

Hints

Problem Source

Codeforces 1253D Harmonious Graph

Subtasks

No.	Testdata Range	Score
1	0~19	100

Testdata and Limits

No.	Time Limit (ms)	Memory Limit (KiB)	Output Limit (KiB)	Subtasks
0	1000	65536	65536	1
1	1000	65536	65536	1
2	1000	65536	65536	1
3	1000	65536	65536	1
4	1000	65536	65536	1
5	1000	65536	65536	1
6	1000	65536	65536	1
7	1000	65536	65536	1
8	1000	65536	65536	1
9	1000	65536	65536	1
10	1000	65536	65536	1
11	1000	65536	65536	1
12	1000	65536	65536	1
13	1000	65536	65536	1
14	1000	65536	65536	1
15	1000	65536	65536	1
16	1000	65536	65536	1
17	1000	65536	65536	1
18	1000	65536	65536	1
19	1000	65536	65536	1

Submit

Status

Ranklist

29 . 和諧的圖