====== کم‌تر رنگ‌آمیزی ======

گراف جهت‌دار ساده‌ی $G$ با $n$ ‌ راس داده شده است. می‌خواهیم یک رنگ‌آمیزی معتبر از $\{1,…,k\}$  برای راس‌های $G$ بیابیم که $k$ از طول (تعداد راس‌های) بزرگ‌ترین مسیر جهت‌دار در $G$ بیش‌تر نباشد.



===== ورودی =====
در اول فایل ورودی عدد $n$($1 \leq n \leq 10^4$)  و در $n$‌ سطر بعدی ماتریس مجاورت $G$ آمده است.


===== خروجی =====

در فایل خروجی در صورت وجود، عدد نسبت داده شده به هر راس را با یک فاصله بنویسید. در غیر این صورت پیغام $Impossible$ را در فایل خروجی بنویسید.


 
===== محدودیت‌ها =====


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

===== ورودی و خروجی نمونه =====

<WRAP :en>
^  ورودی نمونه  ^  خروجی نمونه  ^
|4 \\ 0 0 1 1 \\ 1 0 0 0 \\ 0 1 0 0  \\ 0 0 0 0|1 2 3 3|
</WRAP><پاسخ>



</پاسخ>


  * [[سوال ۶|سوال بعد]]
  * [[سوال ۴|سوال قبل]]