TopCoder

Omelet
ㄏ一ㄏ一 軟軟好香

User's AC Ratio

94.9% (37/39)

Submission's AC Ratio

47.3% (52/110)

Tags

Description

ㄍㄩ現在在玩鬼腳圖,但是運氣不好的他每次都選到自己不想要的結果,於是他打算研究鬼腳圖,他發現從任兩個不相同的鬼腳圖起點開始都走不到相同的結尾。
興奮的他於是請你構造一個鬼腳圖出來,而他會給你一些一定要的要求,例如從左數來的第一個點一定要走到從左數來的第三個點、左數來的第四個點一定要走到從左數來的第二個點、左數來的第八個點一定要走到從左數來的第一個點...
於是可憐的工具人你幫他構造出了一個鬼腳圖出來,但是ㄍㄩ不是很滿意,因為他是個客家人,而客家人最討厭用太多橫槓在鬼腳圖之中,可憐的你只好重新設計鬼腳圖,並且告訴他他給定的限制最少要幾個橫槓才能完成,讓他可以挑一個最客家的方式拿到他想要的鬼腳圖。

Input Format

第一行輸入兩個正整數$N, M$,分別代表鬼腳圖的大小以及他要求的限制數量
接下來的$M$行每行有兩個正整數$a_i, b_i$代表他要求從從左數來第$a_i$個起點出發要到達從左數來第$b_i$個終點
$M\leq N, 1\leq a_i, b_I\leq N$
$a_i\neq a_j \Leftrightarrow i \neq j, b_i\neq b_j \Leftrightarrow i \neq j$

Output Format

輸出一個正整數代表建立出這張鬼腳圖所需要的最少橫槓數量

Sample Input 1

3 2
1 3
2 2

Sample Output 1

3

Hints

範例測資的一種構造方法


Problem Source

2019 NTU CSIE ADA作業
Problem Set by oToToT

Subtasks

No. Testdata Range Constraints Score
1 0~3 $N\leq 5$ 10
2 4~7 $N\leq 1000, N=M$ 20
3 8~11 $N\leq 1000$ 10
4 12~15 $N=M$ 12
5 16~19 $N\leq 5\times 10^ 5$ 48

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, 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 2
5 1000 65536 65536 2
6 1000 65536 65536 2
7 1000 65536 65536 2
8 1000 65536 65536 3
9 1000 65536 65536 3
10 1000 65536 65536 3
11 1000 65536 65536 3
12 1000 65536 65536 4
13 1000 65536 65536 4
14 1000 65536 65536 4
15 1000 65536 65536 4
16 1000 65536 65536 5
17 1000 65536 65536 5
18 1000 65536 65536 5
19 1000 65536 65536 5