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

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

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

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