المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۱۱:عملی:سوال ۱۹

ترمز بریده

در شهر ترمز بریده‌ها $n$ میدان وجود دارد که با شماره‌های $1...n$ نشان داده می‌شوند. تعدادی خیابان یک‌طرفه بین میدان‌های این شهر وجود دارد که ماشین ما هر خیابان را دقیقا در ۱ دقیقه طی می‌کنند. لیست تمام خیابان‌های شهر و سه عدد $u$ و $v$ و $k$ داده شده است. برنامه‌ی شما باید مشخص کند آیا می‌توان از میدان $u$ با ماشین حرکت کرد و دقیقا $k$ دقیقه بعد در میدان $v$ بود یا نه. در شهر فقط می‌خواهیم در خیابان‌ها حرکت کنیم و از هیچ خیابان ورود ممنوعی عبور نکنیم. در ضمن از آن‌جایی که ماشین ما ترمز ندارد در طول مسیر در هیچ جایی نمی‌توانیم توقف کنیم.

ورودی

در خط اول فایل ورودی به ترتیب اعداد $n$ و $m$ (تعداد خیابان‌ها) و $u$ و $v$ و $k$ و در $m$ خط بعد در هر خط دو عدد آمده که نشان‌دهنده‌ی یک خیابان است. به این صورت که اگر این دو عدد به ترتیب $a$ و $b$ باشند یک خیابان یک‌طرفه از $a$ به $b$ وجود دارد.($1\leq n \leq 100$ و $0\leq k \leq 3000$)

خروجی

در فایل خروجی در صورتی که این کار امکان‌پذیر است $k$ عدد بنویسید که عدد $i$ ام شماره‌ی میدانی است که دقیقا $i$ دقیقه بعد از حرکت در آن بوده‌اید و اگر این کار ممکن نیست پیغام No Impossible را در فایل خروجی بنویسید.

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
4 6 1 4 7
1 2
2 1
1 3
3 2
3 4
4 1
2 1 3 4 1 3 4

ابزار صفحه