بازگشت به دور


  • محدودیت زمان: ۳ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

فامیل دور که در کار در فعالیت دارد، در انتها به شهرش دور بازگشته تا همانطور که از بچگی آرزو داشته به شهرش خدمت کند. دور، شهر بی دفاع، از تعدادی محله تشکیل شده که تعدادی خیابان بینشان وجود دارد. از ویژگی های ممتاز دور که اهالی دور به آن افتخار می‌کنند این است که اگر حداقل ۴ محله مختلف را دور یک دایره قرار دهیم به طوری که بین هر دو محله که دور دایره کنار هم قرار گرفته اند خیابانی وجود داشته باشد، حداقل یک خیابان وجود دارد که دو تا از این محله ها که دور دایره کنار هم قرار نگرفته اند را به هم وصل کند.

در اولین قدم مسئولیت ساماندهی مرکز شهر به فامیل محول شده است. مرکز شهر را تعدادی محله تشکیل می‌دهند که بین هر دوتایشان خیابان وجود داشته باشد و تعداد این محله ها بیشینه مقدار ممکن باشد. فامیل می‌خواهد تعداد محله های مرکز شهر را بفهمد تا پیش‌بینی های لازم را انجام دهد. او از شما کمک می‌خواهد تا بتواند از اولین ماموریت در خدمت به شهرش سربلند بیرون بیاید.

مثال🔗

ورودی🔗

در سطر اول ورودی دو عدد nn و mm می‌آید که نشان دهنده تعداد محله‌ها‌ و تعداد خیابان‌های شهر دور است. در ادامه mm سطر می‌آید که در iiمین آن‌ها دو عدد aia_i و bib_i می‌آید که نشان دهنده وجود خیابان بین محله های aia_i و bib_i است. تضمین می‌شود که بین هر دو محله حداکثر یک خیابان وجود دارد. 1n,m1 000 000 1 \le n, m \le 1\ 000\ 000 1mn(n1)2 1 \le m \le \frac {n (n - 1)} 2 1ai,bin 1 \le a_i, b_i \le n aibi a_i \neq b_i

خروجی🔗

در تنها سطر خروجی تعداد محله های مرکز شهر باید چاپ شود.

ورودی نمونه ۱🔗

5 8
1 2
2 3
3 4
4 5
5 1
1 3
1 4
3 5
Plain text

خروجی نمونه ۱🔗

4
Plain text

ورودی نمونه ۲🔗

6 7
1 2
2 3
2 4
2 5
5 1
5 4
5 6
Plain text

خروجی نمونه ۲🔗

3
Plain text
ارسال پاسخ برای این سؤال
در حال حاضر شما دسترسی ندارید.