حافظه‌ی کامپیوترها همواره قابل اتکا نیست و گاهی اوقات محتوای یک کلمه‌ی حافظه می‌تواند مخدوش باشد. این موضوع می‌تواند به خاطر اشتباه در تولید، قطع برق یا شرایط محیطی مانند نویز و دمای زیاد باشد. به عنوان نمونه، فرض کنید که شما یک درخت دودویی جستجو (ددج) از اعداد حقیقی دارید که بتوانید بعضی عملیات را سریع‌تر انجام دهید. یک ددج ساختمان داده‌ای به شکل درخت دودویی است که این ویژگی‌ها را دارد: به ازای هر گره با کلید $x$ (۱) زیردرخت چپ آن تنها شامل گره‌هایی می‌شود که کلیدشان کمتر از $x$ باشد، (۲) زیردرخت راست آن تنها شامل گره‌هایی می‌شود که کلیدشان بیشتر از $x$ باشد، (۳) زیردرخت‌های چپ و راست آن هم ددج باشند و (۴) کلیدهای تکراری مجاز نیست. یک ددج با اندازه ۹ در زیر نمایش داده شده است (شکل سمت چپ). اگر به علت خطای حافظه مقدار ۱۱ به ۷ تغییر یابد (شکل سمت راست)، ددج نامعتبر می‌شود، یعنی بعضی ویژگی‌های ددج دیگر صادق نیستند. در ددج نامعتبر زیر (شکل سمت راست) جستجوی ۹ از مسیر اشتباهی طی می‌شود و پاسخ غلط گزارش می‌دهد.







برای معتبر نگه داشتن یک ددج، می‌توان ددج را مرتباً بررسی کرد و آن را به یک ددج معتبر تبدیل کرد (البته اگر نامعتبر باشد). یک راه ساده برای معتبر کردن یک ددج این است که تعدادی گره انتخاب کنیم (نه لزوما آن‌هایی که کلیدشان به خاطر خطای حافظه تغییر یافته) و مقدار کلیدشان را به مقادیر مناسبی تغییر دهیم که ددج معتبر شود. از آن جا که می‌خواهیم تعداد کمی از کلیدها را تغییر دهیم، شما باید کمینه تعداد گره‌هایی را محاسبه کنید که تغییر کلید آن‌ها ددج را معتبر می‌کند.

ورودی شامل چندین مورد آزمون می‌باشد. برای هر مورد آزمون یک ددج به صورت زیر داده شده است. خط اول شامل یک عدد $n \leq 50,000$ است که اندازه ددج می‌باشد. در هر یک از $n-1$ خط بعدی سه فقره با فاصله از یکدیگر جدا شده‌اند که یک گره را مشخص می‌کنند. اولین فقره کلید ذخیره شده در گره است، دومین فقره کلید ذخیره‌ شده در پدر گره است و در نهایت آخرین فقره یا «L» یا «R» است که مشخص می‌کند که گره فرزند چپ («L») یا فرزند راست («R») پدرش است. همه کلیدها اعداد نامنفی صحیح (حداکثر $10^6$) و متفاوت هستند اما توجه کنید که کلیدهای ذخیره شده در یک ددج معتبر می‌توانند اعداد حقیقی باشند. ورودی با یک خط شامل «0» خاتمه می‌یابد.

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

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

• سوال بعد
• سوال قبل