گراف جهتدار سادهی G با n راس داده شده است. میخواهیم یک رنگآمیزی معتبر از {1,…,k} برای راسهای G بیابیم که k از طول (تعداد راسهای) بزرگترین مسیر جهتدار در G بیشتر نباشد.
در اول فایل ورودی عدد n(1≤n≤104) و در n سطر بعدی ماتریس مجاورت G آمده است.
در فایل خروجی در صورت وجود، عدد نسبت داده شده به هر راس را با یک فاصله بنویسید. در غیر این صورت پیغام Impossible را در فایل خروجی بنویسید.