Farmer John は $N$ 個（$1 \le N \le 1{,}000$）の納屋（番号 $1..N$）を新しい光ファイバー網で結びたいと考えます。大きな池の縁に円状に並ぶため、隣接する納屋だけを結べます。納屋 $N$ と 1 も隣接します。
通信したい牛の対は限られ、全納屋を結ぶ必要はありません。すべての要求対が網を通じて通信できるよう、接続を最小にします。要求の一覧から最小線数を求めてください。納屋 1 から 3 に通信するには、1 と 2、および 2 と 3 の線を敷きます。
入力
第 $1$ 行：整数 $N$ と $P$。後者は通信対の数（$1 \le P \le 10{,}000$）。
第 $2..P+1$ 行：通信したい納屋の対を表す整数二つ。重複対はありません。
出力
最小の直接接続数を整数一つ、一行に出力。
入出力例
入力 1
5 2
1 3
4 5出力 1
3注記
納屋の対 1-2、2-3、4-5 を結びます。
問題提供：Reid Barton、2001。