يريد 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.