원형 네트워크

N개의 컴퓨터가 원형으로 연결되어 있다. 컴퓨터 번호는 1부터 N까지이며, x번 컴퓨터는 양옆의 컴퓨터와 회선으로 연결된다. 1번과 N번도 서로 연결되어 있으므로 전체 회선은 하나의 원을 이룬다.

일부 회선을 광섬유로 전환하려고 한다. p번 컴퓨터와 q번 컴퓨터 사이에 광섬유 경로를 만들어 달라는 요청이 P개 주어진다.

한 요청을 만족시키려면 p와 q를 잇는 두 방향 중 하나를 골라, 그 경로에 있는 모든 회선을 광섬유로 전환하면 된다. 예를 들어 N=3이고 1번과 2번을 연결해야 한다면, 1-2 회선 하나를 전환할 수도 있고 2-3, 3-1 회선을 전환할 수도 있다.

모든 요청을 만족시키기 위해 광섬유로 전환해야 하는 회선 수의 최솟값을 구하라.

첫째 줄에 두 정수 N과 P가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ P ≤ 10,000)

다음 P개의 줄에는 요청을 나타내는 두 컴퓨터 번호 p와 q가 주어진다.

첫째 줄에 모든 요청을 만족시키는 데 필요한 최소 회선 수 X를 출력한다.