مسابقه تمرینی برنامه نویسی جمعی از دانشجویان پیام نور هشتگرد

تقاطع‌های حیاتی


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

کیانوش متقاضی عضویت در سازمان OC است. در روز چهارم مصاحبه، سازمان دور‌اندیشی او را مورد بررسی قرار داده است.

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

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

ورودی🔗

سطر اول ورودی تنها شامل دو عدد nn و mm است که نمایانگر تعداد تقاطع‌ها و تعداد خیابان‌های شهر است.

سپس در iiمین سطر از هریک از mm سطر بعدی، دو عدد uiu_i و viv_i آمده است که یعنی خیابانی از تقاطع شماره uiu_i به سمت تقاطع شماره viv_i وجود دارد. میتوانید فرض کنید بین هردو تقاطع حداکثر یک خیابان در یک جهت وجود دارد.

1n50001 \le n \le 5000

n1m2×105n - 1 \le m \le 2 \times 10^5

خروجی🔗

سطر اول خروجی باید شامل یک عدد kk باشد که نمایانگر تعداد تقاطع‌های حیاتی هستند. سپس در سطر دوم شماره این تقاطع‌ها را به ترتیب صعودی خروجی دهید.

ورودی نمونه🔗

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

خروجی نمونه🔗

2
1 2
Plain text

در این مثال با انسداد تقاطع شماره ۱ از شهرداری به هیچیک از دیگر تقاطع‌ها نمیتوان رفت. درصورت انسداد تقاطع ۲ هم نمیتوان به تقاطع ۳ رسید.

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