- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
یک گراف ساده به نام \(G\) با \(n\) راس و \(m\) یال داریم. راسهای این گراف با اعداد \(1\) تا \(n\) شمارهگذاری شدهاند. در هر عملیات میتوانیم یکی از دو عدد صحیح و مثبت مثل \(u\) و \(v\) را انتخاب کنیم به طوری که \(1 \leq u \neq v \leq n\) و یکی از دو عملیات زیر را انجام دهیم اگر یال \(uv\) در \(G\) موجود است، آن را حذف کنیم. اگر یال \(uv\) در \(G\) موجود نیست، آن را به \(G\) اضافه کنیم.
میخواهیم با این عملیاتها \(G\) را به یک درخت، تبدیل کنیم. به شما گراف \(G\) داده میشود و از شما میخواهیم کمترین تعداد عملیات لازم برای تبدیل \(G\) به یک درخت را محاسبه کنید.
ورودی
در سطر اول ورودی، دو عدد صحیح \(n\) و \(m\) که با یک فاصله از هم جدا شدهاند، داده میشود.
\[1 \leq n \leq 100 \, 000\] \[0 \leq m \leq 500 \, 000\]
در \(m\) سطر بعدی، در هر سطر، دو عدد صحیح \(u\) و \(v\) که با یک فاصله از هم جدا شدهاند داده میشود. \(uv\) یک یال از \(G\) است.
\[1 \leq u \lt v \leq n\]
خروجی
کمترین تعداد عملیات لازم برای تبدیل \(G\) به یک درخت.
مثالها
ورودی نمونه ۱
5 4
1 2
1 3
2 3
4 5
خروجی نمونه ۱
2
ورودی نمونه ۲
3 2
1 2
1 3
خروجی نمونه ۲
0