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行每行有兩個正整數ai,bi代表他要求從從左數來第ai個起點出發要到達從左數來第bi個終點
MN,1ai,bIN
aiajij,bibjij

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 N5 10
2 4~7 N1000,N=M 20
3 8~11 N1000 10
4 12~15 N=M 12
5 16~19 N5×105 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