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