• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۱۰۲۴ مگابایت

---

• بخش تعریفی این سوال، تا جهت‌دهی اولییه راهروها با سوال سالن‌های ذخیره طلا یکسان است. اما این دو سوال متفاوت‌اند.

نقشه سالن‌های ذخایر طلای میلی به ما داده شده است. \(n\) سالن داریم و این سالن‌ها با \(n-1\) راهرو به هم متصل شده‌اند و از تمام سالن‌ها به همه سالن‌ها می‌توان رسید (مانند یک درخت در دنیای گراف‌ها).

از آنجا که امنیت برای ما خیلی مهم است نمی‌خواهیم دسترسی سالن‌ها به یکدیگر زیاد باشد. به همین منظور، می‌خواهیم راهروها را یک طرفه کنیم به شکلی که فقط از یک سالن در یک طرف راهرو بتوان به سالن دیگر رفت و برعکس آن امکان پذیر نباشد.

بعد از یک طرفه کردن راهروها، عدد ضعف هر سالن را تعریف می‌کنیم، تعداد سالن‌هایی که می‌توان با استفاده از راهروها در جهت تایین شده، به آنها رسید. رومینا برای بازپرسی آمده است و عدد ضعف سالن‌ها را روی یک کاغذ نوشته است. او به اندازه بیشترین اختلاف بین دو عدد از اعداد نوشته شده، تعجب می‌کند و نقشه را ناهمسان می‌خواند.

خود شرکت میلی بعضی راهروها را جهت‌دهی کرده است و جهت این راهروها قابل تغییر نیست. شما باید بقییه راهروها را طوری جهت‌دهی کنید که نقشه در کمینه تعجب رومینا را به همراه داشته باشد.

ورودی

در خط اول ورودی تعداد تست‌کیس ها \(T\) می‌آید.

ورودی هر تست‌کیس شامل دو خط است. در خط اول ورودی تعداد سالن‌های ذخایر طلای میلی \(n\)، می‌آید.

می‌دانیم نقشه سالن‌ها در هر تست کیس یک درخت است که راس‌های آن سالن‌ها هستند یال‌های این درخت نیز راهروها هستند. درخت مفروض را از راس منتصب به سالن \(1\) ریشه‌دار کرده‌ایم. این درخت ریشه‌دار شده در خط دوم ورودی، به شما ورودی داده می‌شود.

در \(n-1\) خط بعدی هر تست کیس اطلاعات یال‌ها داده می‌شوند. در \(i\) امین خط (\(2 \le i \le n\))، به ترتیب عدد \(par_i\) و سپس کاراکتر \(c_i\) می‌آید. که نشان‌دهنده پدر راس منتصب به سالن \(i\) است. یعنی بین سالنهای \(par_i\) و \(i\) یک راهرو وجود دارد و به طور متناظر بین این دو راس نیز در درخت یال کشیده شده است. اگر \(c_i\) برابرD باشد، جهت این یال از پدر به سمت \(i+1\) است و اگر U باشد،جهت این یال از \(i\) به سمت \(par_i\) است و نهایتا اگر برابر ? باشد، جهت آن نامعلوم است و شما باید آن را جهت‌دهی کنید. \[1 \le n \le 500\] \[1 \le par_i < i\] \[c_i \in \{ U, D, ? \}\]

تضمین می‌شود جمع \(n\) های هر تست حداکثر \(500\) باشد.

خروجی

به ازای هر تست‌کیس، کمیته تعجب ممکن رومینا رابعد از جهت‌دهی سالن‌های ذخیره طلا در تنها یک خط خروجی دهید.

مثال

ورودی نمونه ۱

2
3
1 ?
1 ?
5
1 D
1 ?
2 D
2 ?

خروجی نمونه ۱

1
3