- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
- بخش تعریفی این سوال، قبل از روش جهتدهی راهروها با سوال سالنهای ذخیره طلا در شرایط حساستر یکسان است. اما هدف سوال متفاوت است.
نقشه سالنهای ذخایر طلای میلی به ما داده شده است. \(n\) سالن داریم و این سالنها با \(n-1\) راهرو به هم متصل شدهاند و از تمام سالنها به همه سالنها میتوان رسید (مانند یک درخت در دنیای گرافها).
از آنجا که امنیت برای ما خیلی مهم است نمیخواهیم دسترسی سالنها به یکدیگر زیاد باشد. به همین منظور، میخواهیم راهروها را یک طرفه کنیم به شکلی که فقط از یک سالن در یک طرف راهرو بتوان به سالن دیگر رفت و برعکس آن امکان پذیر نباشد.
بعد از یک طرفه کردن راهروها، ضعف نقشه را تعریف میکنیم تعداد جفت مرتب سالنهایی که به هم مسیر دارند (میتوان از سالن اول با استفاده از راهروها در جهت تایین شده به سالن دوم رسید). به شما نقشه اولیه سالنها و راهروها داده شده است و شما باید راهروها را طوری جهتدهی کنید که نقشه در نهایت کمینه ضعف را داشته باشد.
ورودی
ورودی شامل دو خط است. در خط اول ورودی تعداد سالنهای ذخایر طلای میلی \(n\)، میآید.
میدانیم نقشه سالنها یک درخت است که راسهای آن سالنها هستند یالهای این درخت نیز راهروها هستند. درخت مفروض را از راس منتصب به سالن \(1\) ریشهدار کردهایم. این درخت ریشهدار شده در خط دوم ورودی، به شما ورودی داده میشود.
در خط دوم ورودی \(n-1\) عدد متوالی به شکل \(par_2, par_3, \ldots, par_n \ \) میآید که \(par_i\) نشاندهنده پدر راس منتصب به سالن \(i\)، در درخت ریشهدار شده است. این به این معنی است که بین سالن \(i\) و و سالن \(par_i\) یک راهرو وجود دارد.
محدودیتها
\[ 1 \le n \le 2 \times 10^5 \] \[ 1 \le par_i < i \]
خروجی
در خط اول خروجی کمینه ضعف را خروجی دهید.
سپس در خط دوم خروجی یک رشته شامل \(n-1\) کاراکتر خروجی دهید که کاراکتر \(i\) ام نشاندهندهی جهت یال بین راس منتصب به سالن\(i+1\) ام و پدرش است. اگر این کاراکتر U باشد یعنی این یال از خودش به سمت پدرش جهت دار شده است، و اگر D باشد یعنی این یال از سمت پدرش به سمت خودش جهت دار شده است.
اگر چند جواب با کمینه تاریکی وجود داشت، رشتهای را خروجی دهید که لکسیکوگرافیکالی کمینه باشد.
مثال
ورودی نمونه ۱
3
1 2
خروجی نمونه ۱
2
DU