+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت ---------- یک گراف ساده به نام $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 ``` <details class="blue"> <summary> **راهنمایی اول** </summary> ---------- گراف $G$ درخت است اگر و تنها اگر همبند باشد و هیچ دوری نداشته باشد. </details> <details class="blue"> <summary> **راهنمایی دوم** </summary> ---------- اگر $G$ دارای $c$ مولفه‌ی همبندی باشد، به حداقل $c - 1$ یال نیاز داریم که آن را همبند کنیم. اگر یک مولفه‌ی همبندی $G$ دارای $n_i$ راس و $m_i$ یال باشد، باید یک زیردرخت فراگیر آن که شامل $n_i - 1$ یال است را نگه‌داریم و $m_i - n_i + 1$ یال دیگر را از آن مولفه‌همبندی حذف کنیم. (با وجود این یال‌ها دور گراف به‌وجود می‌آید.) </details> <details class="blue"> <summary> **راهنمایی سوم** </summary> ---------- اگر مجموع یال‌های مورد نیاز برای حذف را محاسبه کنید،‌ می‌بیند که فقط به مقدار $c$ نیاز دارید و می‌توانید آن را با استفاده از الگوریتم‌های مثل *dfs، bfs* یا *dsu* بدست آورید. </details>

حل سؤال در بانک سؤالات