====== طولانی ====== گراف جهت‌دار بدون دور $G$ و دو راس $s$ و $t$ از راس‌های $G$ به ما داده شده است. توجه کنید که گراف $G$‌ دور جهت‌دار ندارد ولی ممکن است اگر جهت یال‌ها را برداریم دور پیدا کند. هدف این سوال پیدا کردن گرافی است(که آن را $H$ می‌نامیم) که راس‌های آن راس‌های $G$ است و یال‌هایش اجتماع همه‌ی یال‌های تمام طولانی‌ترین مسیرها از $s$ به $t$ در $G$ است. ===== ورودی ===== در سطر اول فایل ورودی، $n$ تعداد راس‌های گراف سپس شماره‌ی راس $s$ و راس $t$ به همین ترتیب آمده است. در $n$ سطر بعدی ماتریس مجاورت $G$ نوشته شده.(فرض کنید از تمام راس‌ها به $s$ مسیری وجود دارد و $n\leq 1000$.) ===== خروجی ===== در فایل خروجی ماتریس مجاورت $H$ را بنویسید. ===== محدودیت‌ها ===== * محدودیت زمان: ۳ ثانیه * محدودیت حافظه: ۲۵۶ مگابایت ===== ورودی و خروجی نمونه ===== ^ ورودی نمونه ^ خروجی نمونه ^ |5 1 5 \\ 0 1 1 0 0 \\ 0 0 1 1 1 \\ 0 0 0 0 1 \\ 0 0 0 0 1 \\ 0 0 0 0 0| 0 1 0 0 0 \\ 0 0 1 1 0 \\ 0 0 0 0 1 \\ 0 0 0 0 1 \\ 0 0 0 0 0| * [[سوال ۹|سوال بعد]] * [[سوال ۷|سوال قبل]]