Processing math: 100%

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۸:عملی:سوال ۱۳

رنگ‌آمیزی مرتب

درخت n راسی T داده شده است. درجه‌ی راس i ام این درخت را با di نشان می‌دهیم. منظور از رنگ‌آمیزی مرتب یالی T تخصیص رنگ‌هایی با شماره‌های عددی به یال‌های آن است به‌طوری‌که رنگ‌های یال‌های متصل به راس i ام درخت، از مجموعه‌ی {1,2,...,di} انتخاب شوند و هیچ دو یال مجاوری هم‌رنگ نباشند. برنامه‌ای بنویسید که در حداکثر زمان ۱۰ ثانیه در صورت امکان یک‌ رنگ‌‌آمیزی مرتب یالی برای درخت T‌ بیابد.

ورودی

فایل ورودی شامل n خط است؛ در خط اول آن n و در خطوط بعدی، در هر سطر شماره‌ی دو راس مربوط به یک یال نوشته شده است. فرض کنید n از ۱۰۰ بیش‌تر نیست.

خروجی

در صورت وجود جواب فایل خروجی باید شامل n1 عدد طبیعی باشد و رنگ مربوط به یال‌ها به همان ترتیبی که در ورودی آمده‌اند، در آن نوشته شده باشد. اگر مسئله جواب نداشت، در این فایل رشته‌ی No Solution را چاپ کنید.

ورودي و خروجي نمونه

ورودي نمونه خروجي نمونه
4
1 2
2 3
3 4
1
2
1

ابزار صفحه