گراف جهت‌دار بدون دور $G$ و دو راس $s$ و $t$ از راس‌های $G$ به ما داده شده است. توجه کنید که گراف $G$‌ دور جهت‌دار ندارد ولی ممکن است اگر جهت یال‌ها را برداریم دور پیدا کند. هدف این سوال پیدا کردن گرافی است(که آن را $H$ می‌نامیم) که راس‌های آن راس‌های $G$ است و یال‌هایش اجتماع همه‌ی یال‌های تمام طولانی‌ترین مسیرها از $s$ به $t$ در $G$ است.

در سطر اول فایل ورودی، $n$ تعداد راس‌های گراف سپس شماره‌ی راس $s$ و راس $t$ به همین ترتیب آمده است. در $n$ سطر بعدی ماتریس مجاورت $G$ نوشته شده.(فرض کنید از تمام راس‌ها به $s$ مسیری وجود دارد و $n\leq 1000$.)

در فایل خروجی ماتریس مجاورت $H$ را بنویسید.

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

• سوال بعد
• سوال قبل