2146 . 鬼鬼鬼鬼鬼腳圖的拉
TopCoder
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
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 |