Maverick 사냥

21XX년이다. 한 세기를 기다린 끝에 드디어 Xbox 1024에서 새로운 Mega Man X 게임을 플레이할 수 있게 되었다. 평소처럼 레벨은 $n$개이며 1번부터 $n$번까지 번호가 붙어 있고, 각 레벨은 Maverick이라는 타락한 로봇과의 전투로 끝난다. Maverick을 쓰러뜨리면 게임이 끝날 때까지 그 Maverick의 무기를 사용할 수 있다. 각 Maverick은 번호상 바로 이전 레벨에서 얻는 무기에 약하다. 레벨 2의 Maverick은 레벨 1의 무기에 약하고, 레벨 $n$의 Maverick은 레벨 $n-1$의 무기에 약하다. 예외는 레벨 1의 Maverick으로, 레벨 $n$의 무기에 약하다. 일부 레벨에는 아머 업그레이드가 있으며, 전체 개수는 $m$개다. 아머 업그레이드 $i$는 레벨 $l_i$에 있고, 이를 얻으려면 레벨 $w_i$의 무기가 필요하다. 단, $w_i \neq l_i$이다. 한 번의 레벨 진행에서 잠금을 풀 수 있는 무기만 있다면 아머 업그레이드를 몇 개든 모을 수 있다. 백트래킹을 싫어하므로 각 레벨은 한 번씩만 지나가며, 그 자리에서 얻을 수 없는 아머 업그레이드는 그냥 둔다. 게임을 쉽게 하기 위해, 이미 가진 무기에 약한 Maverick이 있는 레벨만 고르기로 한다. 시작 레벨은 아무 곳이나 고를 수 있고, 시작할 때 약점 무기를 가지고 있을 필요는 없다. 시작 레벨을 고른 뒤에는 레벨을 순서대로 진행한다 (레벨 $n$에서 레벨 1로 내려가는 것도 순서에 포함). 모든 레벨을 정확히 한 번씩 깰 때까지 이 과정을 반복한다. 이 방식으로는 아머 업그레이드를 많이 놓칠 수 있고, 최종 보스는 매우 강하다. 가능한 한 효율적으로 게임을 깨고 싶으니, 놓치게 되는 아머 업그레이드의 최소 개수를 구하는 프로그램을 작성하라.

첫 줄에 두 정수 $n$과 $m$ ($2 \leq n \leq 10^5$, $1 \leq m \leq 10^5$)이 주어진다. 각각 레벨 수와 아머 업그레이드 수다. 이어지는 $m$개의 줄에는 정수 $w_i$와 $l_i$ ($1 \leq w_i, l_i \leq n$, $w_i \neq l_i$)가 주어진다. $w_i$는 아머 업그레이드 $i$의 잠금을 풀 때 필요한 무기가 있는 레벨이고, $l_i$는 아머 업그레이드 $i$가 있는 레벨이다.

놓치게 되는 아머 업그레이드 개수의 최솟값을 출력한다.