جزایر
Problem
یک ایالت پراکنده در جزایر اقیانوسیه تصمیم گرفت شبکه ای از جاده ها (یا بهتر بگوییم پل ها) ایجاد کند. هر پل را می توان در هر دو جهت پیمایش کرد. یک طرح توالی برای ساخت پل ها تدوین شده است و مشخص است که پس از ساخت همه پل ها، می توان از هر جزیره به هر یک از آنها (شاید از طریق برخی جزایر میانی
) عبور کرد.
با این حال، این لحظه ممکن است قبل از ساخته شدن همه پل ها فرا برسد. شما باید چنین حداقل تعداد پل را تعیین کنید که پس از ساخت آنها (به ترتیب تعیین شده توسط طرح)، امکان دسترسی از هر جزیره به هر جزیره دیگری وجود خواهد داشت.
ورودی
خط اول شامل دو عدد است: تعداد جزایر N (1≤N≤10000) و تعداد پل‌های طرح M (1≤M≤50000). سپس خطوط M وجود دارد که هر کدام شامل دو عدد x و y (1≤x,y≤N) هستند - اعداد شهرهایی که توسط پل بعدی در طرح به هم متصل شده‌اند.
خروجی
این برنامه باید یک عدد واحد تولید کند - حداقل تعداد پل های ساخته شده، که پس از آن می توان از هر جزیره به هر جزیره دیگری رفت.
<بدن>
| ورودی |
خروجی |
|
4 5
1 2
1 3
2 3
3 4
4 1
|
4 |