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

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