SPOJ in Armenian

Շրջանագիծը K կետերի միջոցով բաժանված է K հավասար մասերի։ Կետերը համարակալված են ժամացույցի սլաքի հակառակ ուղղությամբ սկսած ամենավերևի կետից (տես նկարը)։ M կետերի զույգեր միացված են իրար լարերով։ Լարը նկարագրվում է իր ծայրակետերի համարներով։

Պահանջվում է գրել ծրագիր, պարզելու համար, թե ամենաքիչը քանի լար է պետք ջնջել, որպեսզի մնացած լարերն իրար հետ չհատվեն։ (Այս խնդրում հատում ասելով հասկանում ենք հատումը ներքին կետերում։)

Նկարում բերված օրինակում K=7, M=4: Եթե հանենք 3 և 7 ծայրակետերով լարը, մնացած լարերը չեն հատվի։

Մուտքը

Մուտքի առաջին տողում տրված են K (2 ≤ K ≤ 1 000 000 000) և N(1 ≤ N ≤ 5 000) ամբողջ թվերը։ Հաջորդ N տողերից յուրաքանչյուրը նկարագրում է մի լար և պարունակում է 2 ամբողջ Ai և Bi (1 ≤ Ai, Bi ≤ K) թվեր՝ համապատասխան լարի ծայրակետերի համարները։ Հայտնի է, որ

• Ai ≠ Bi
• Ai ≠ Аj կամ  Bi ≠ Bj , եթե i ≠ j

Ելքը

Հարկավոր է արտածել մի թիվ, որը ցույց տա, թե առնվազն քանի լար է պետք ջնջել։

Օրինակ

Մուտքը.
7 4
1 6
3 7
2 4
6 4

Ելքը.
1