• هفدهمین مسابقه‌ی برنامه نویسی اینترنتی ایران
  • مقدماتی منطقه‌ی غرب آسیا، سایت تهران
  • دانشگاه صنعتی شریف، ۷ آذر ۱۳۹۸

لینک‌های مفید برای شرکت در مسابقه:

جاده‌فروشی


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

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

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

دولت قصد دارد تا با بیشترین تعداد شرکت ممکن قرارداد ببندد تا سود خود از این طرح را بیشینه کند. برای کمک به دولت حداکثر تعداد شرکت ممکن برای قرارداد را اعلام کنید.

ورودی🔗

در خط اول ورودی، دو عدد nn (تعداد شهرهای پشمکستان) و mm (تعداد جاده های پشمکستان) آمده است.

1n,m1051 \leq n, m \leq 10^5

در خط دوم، دو عدد ss و tt آمده‌اند که شماره‌ی پایتخت‌های پشمکستان هستند. (شهر های پشمکستان از ١ تا nn شماره‌گذاری شده‌اند.)

1s,tn1 \leq s, t \leq n

در هرکدام از mm خط بعدی، دو عدد aa و bb آمده است. به این معنی که جاده‌ای دو طرفه میان شهرهای aa و bb وجود دارد.

1a,bn1 \leq a, b \leq n

خروجی🔗

در تنها خط خروجی، حداکثر تعداد شرکتی را چاپ کنید که دولت می‌تواند با آن‌ها قرارداد ببندد.

مثال‌ها🔗

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

4 4
1 4
1 2
1 3
2 4
3 4
Plain text

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

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