کادو برای فروش

در شهر لی‌لی‌پوت روز سوم مردادماه روز خاصی با نام ‎«روز کادودهی‎» است‎!‎ در این روز هر کدام از مردم شهر به ‎«عزیزترین دوست»اش که در همان شهر زندگی می‌کند (در صورت وجود) کادو می‌دهد. از آن‌جا که همه‌ی مردم این شهر از این مراسم خبر دارند، هر کسی روز دوم مرداد (یک روز قبل از روز کادودهی) پشت در خانه‌اش نام کادوی موردعلاقه‌اش و قیمت آن کادو را می‌نویسد تا اگر کسی دوستش داشت، آن کادو را برایش بخرد‎!‎

دقت کنید که هر کس حداکثر یک دوست ‎«عزیزترین»‎ دارد که می‌خواهد برایش کادو بخرد و هم‌چنین هر نفر حداکثر از یک شخص کادو می‎‌گیرد ( به‌عبارت دیگر، هرکس بعد از این‌که برای اولین بار کادو گرفت، دیگر در خانه‌اش را به‌روی کسی باز نمی‌کند!). اما از آن‌جا که همه‌ی مردم شهر لی‌لی‌پوت ثروتمند نیستند، ممکن‌ست پول بعضی از آن‌ها به خرید کادوی موردعلاقه‌ی عزیزترین دوست‎‌شان (که همواره حداکثر یک نفر خاص‎‎ است) نرسد.

با اطلاع از این موضوع، سمسار شهر لی‌لی‌پوت (که مرد ناقلایی است!)، اعلام کرده که در روز کادودهی حاضرست هر کادوی نویی را به‌صورت کاملاً محرمانه و به‌مبلغ ‎$\rfloor$‎ یک دهم قیمت اصلی‌اش‎ $\lfloor$‎ بخرد‎!‎ با این وصف، اگر برای مثال ‎$A$‎ بخواهد برای ‎$B$ (که عزیزترین دوستش است) کادو بخرد و ‎$B$‎ نیز برای ‎$C$‎؛ و قیمت کادوهای موردعلاقه‌ی ‎$A$‎، ‎$B$‎ و ‎$C$‎ به‌ترتیب ‎۱۰۰۰‎ و ‎۲۰۰۰‎ و ‎۱۵۰۰‎ سکه و دارایی آن‌ها نیز به‌ترتیب ‎۲۱۰۰‎ و ‎۱۴۰۰‎ و صفر سکه باشد، در آن‌صورت ‎$B$‎ می‌تواند صبر کند تا ‎$A$‎ برایش کادو بخرد (به ارزش دو هزار سکه) بعد آن را به سمسار بفروشد (به ارزش دویست سکه‎(!‎ تا با پول خودش بشود ‎۱۶۰۰‎ سکه و بتواند کادوی ‎۱۵۰۰‎ سکه‌ای ‎$C$‎ را برایش بخرد‎!‎

برنامه‌ای بنویسید که

• تعداد افراد و هم‌چنین سرمایه، ارزش کادو و نام عزیزترین دوست هر یک از افراد را از ورودی بخواند؛
• ‎ تعیین کند‎‎‎ حداکثر چند بار عمل ‎«کادو دادن»‎ در روز کادودهی می‌تواند انجام شود. برای یافتن این حداکثر، می‌توانید فرض کنید ترتیب کادو دادن‌ها و اختیار مردم لی‌لی‌پوت کاملاً دست شماست‎!‎
• ‎ این حداکثر را به‌همراه یک روش انتخاب این تعداد و ترتیبِ دادن کادوهایشان در ‎خروجی بنویسد.

• هر تست شامل تعدادی سناریو است. در سطر اوّل ورودی تعداد سناریوهای تست آمده است.
• در سطر اول هر سناریو، تعداد مردمان شهر لی‌لی‌پوت ‎($n$)‎ نوشته شده‌است.
• در هر یک از ‎$n$‎ سطر بعدی، در سطر شماره‌ی ‎$1 \le i \le n$‎، ابتدا دارایی نفر ‎$i$‎ یعنی ‎$c_i$‎، سپس ارزش کادوی مورد علاقه‌اش یعنی ‎$p_i$‎ و نهایتاً شماره‌ی عزیزترین دوست وی یعنی ‎$w_i$‎ می‌آید. می‌دانیم در صورتی که یک نفر ‎«عزیزترین دوست‎» نداشته باشد (و طبعاً هرگز کادو ندهد)، ‎$w_i$‎ وی برابر صفر نوشته شده است.
• همواره ‎$1 \le n \le 10^5$‎ است و در ‎۵۰‎ درصد تست‌ها در تمام سناریوها ‎$1 \le n \le 10^3$‎ است.
• برای هر ‎$1 \le i \le n$‎ می‌دانیم ‎$1 \le c_i‎, ‎p_i \le 10^9$‎ و ‎$ 0 \le w_i \le n$‎ و ‎$w_i \ne i$‎.
• تمام اعداد ورودی و خروجی صحیح ‎ اند.

• به ازای هر سناریوی ورودی، ابتدا در یک سطر در خروجی، حداکثر تعداد افرادی که کادو می‌دهند ‎($m$)‎ را بنویسید.
• سپس در سطر بعدی شماره‌ی ‎$m$‎ نفری که کادو می دهند را به‌ترتیب زمان (از چپ به راست) بنویسید. دقّت کنید که شماره‌ی افراد بین ‎$1$‎ تا ‎$n$‎ است و خروجی مسئله ممکن‌است یکتا نباشد.

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

• سوال بعد