- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
- منبع: آزمون عملی دوره ۲۰ المپیاد کامپیوتر
مهدی به تازگی با نظریه گراف آشنا شده و درختها را مورد بررسی قرار داده است. او به درختهایی علاقهمند است که تعداد برگهایشان از تعداد رئوس غیر برگشان بیشتر است. به همین دلیل او این درختها را درختهای خوب مینامد. با توجه به علاقه شدید او به این خاصیت در درختها او به دنبال درختهایی میگردد که همیشه خوب باشند. او برای اینکه ببیند یک درخت همیشه خوب است، ابتدا بررسی میکند که خود درخت خوب باشد و سپس میخواهد ببیند آیا میتوان راسی را از درخت حذف کرد که جنگل باقیمانده باز هم خوب باقی بماند. او میخواهد آنقدر این کار را بکند تا هیچ راسی در درخت باقی نماند، اگر درختی چنین ویژگیها را داشت، احتمالا مهدی خیلی خوشحال میشود، زیرا یک درخت همیشه خوب یافته است. لازم به ذکر است هنگام حذف کردن یک راس از یک درخت آن راس و همه یالهای مجاورش به همراه رئوسی که درجهشان صفر شده از درخت حذف میشوند.
در این مسئله قرار است شما به مهدی کمک کنید و بگویید آیا یک جنگل همیشه خوب است یا نه و در صورت همیشه خوب بودن ترتیبی از حذف رئوس را ارائه دهید که در همه مراحل جنگل باقیمانده همیشه خوب باقی بماند.
ورودی
در سطر اول ورودی $n$ تعداد رئوس درخت میآید.
در $n$ سطر بعدی در خط $i$ام ابتدا $k$ تعداد رئوس مجاور راس $i$ام میآید و سپس $k$ عدد میآید که شماره رئوس مجاور راس $i$ام میباشند. رئوس از ۱ تا $n$ شمارهگذاری شدهاند.
$$ 1 \le n \le 1\ 000\ 000 $$
خروجی
در سطر اول خروجی اگر درخت ورودی درختی همیشه خوب است، عبارت Always Good Tree
را چاپ نمایید. اگر درخت ورودی، درختی همیشه خوب نیست درتنها خط خروجی عبارت Discouraging Tree
را چاپ نمایید.
در سطر دوم ابتدا تعداد رئوسی که مستقیما حذف میکنید را بنویسید و سپس شماره رئوسی که از درخت حذف کردهاید را به ترتیب حذف شدن بنویسید.
زیرمسئلهها
زیرمسئله | شمارهی تستها | نمره | محدودیت |
---|---|---|---|
۱ | ۱ تا ۵ | ۲۰ | $ n \le 10\ 000 $ |
۲ | ۶ تا ۱۱ | ۸۰ | بدون محدودیت اضافی |
مثال
ورودی نمونه ۱
5
1 2
2 1 3
2 2 4
2 3 5
1 4
خروجی نمونه ۱
Discouraging Tree
ورودی نمونه ۲
5
4 2 3 4 5
1 1
1 1
1 1
1 1
خروجی نمونه ۲
Always Good Tree
1 1
ورودی نمونه ۳
5
2 2 3
1 1
3 1 4 5
1 3
1 3
خروجی نمونه ۳
Always Good Tree
2 1 3
ارسال پاسخ برای این سؤال