+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۲۵۶ مگابایت + آزمون عملی دوم فاینال سی و دومین دوره المپیاد کامپیوتر ایران ---------- سال گذشته در روز کریسمس، کیومرث یک درخت ریشه‌دار $n+1$ راسی با شماره‌های $0$ تا $n$ خرید که ریشه‌ی آن راس شماره $0$ و پدر راس شماره $i$ ام، راس با شماره $p_i$ است. در ابتدا درخت کیومرث به شکل یک مسیر است که درجه راس $0$ در آن یک است و روی هر راس تعدادی نامنفی گوی قرار دارد. کیومرث که از شکل درخت خود ناراضی بود، تصمیم گرفت عملیات زیر را به تعدادی دلخواه روی درختش اعمال کند: + کیومرث در یک عملیات می‌تواند راسی دلخواه مانند $v$ انتخاب کند و پدربزرگش را به عنوان پدرش قرار دهد. به عبارتی $p_v$ بعد از انجام عملیات برابر با $p_{p_v}$ قبل از انجام عملیات خواهد شد. همچنین او به هر راس در زیردرخت $v$ یک گوی اضافه می‌کند. برای انجام عملیات لازم است $v$ پدربزرگ داشته باشد؛ یعنی ریشه یا فرزند ریشه نباشد. حال پس از گذشت یکسال، کیومرث درختی در خانه‌اش پیدا کرده که پدر راس‌هایش $p_1, p_2, \cdots , p_n\ $ و تعداد گوی‌هایشان $a_1, a_2, \cdots , a_n\ $ می‌باشد. اما می‌خواهد بداند که آیا این درخت همان درخت کریسمس است یا خیر. جواب سوال او تنها در صورتی مثبت است که بتوان با شروع از درختی به شکل مسیر و اعمال تعدادی عملیات بر روی آن، به همین درخت برسیم. همچنین در صورت مثبت بودن جواب، مسیری را می‌خواهد پیدا کند که اگر راس‌های آن را به‌ترتیب از ریشه تا آخر بنویسیم، لکسیکوگرافیکالی کمینه باشد. در این سوال شما باید در $Q$ سناریو مختلف، به کیومرث کمک کنید. در هر سناریو باید اعداد $n$ و $T$ و $p_1, p_2, \cdots , p_n\ $ و $a_1, a_2, \cdots , a_n\ $ را ورودی بگیرید، سپس تعیین کنید که آیا مسیر اولیه‌ای وجود دارد یا نه، و در نهایت اگر $T = 1$ بود، مسیر مورد نظر را هم خروجی دهید. # ورودی در خط اول ورودی تعداد سناریو ها $Q$ می‌آید. در هر سناریو در خط اول، دو عدد $n$ و $T$ به ترتیب و با فاصله از هم آمده‌اند. در هر یک از $n$ خط بعدی، دو عدد طبیعی $p_i$ و $a_i$ به‌ترتیب می‌آیند. # خروجی به ازای هر سناریو اگر مسیری وجود داشت، عبارت ```Yes``` و در غیر این صورت، عبارت ```No``` را چاپ کنید. سپس اگر $T = 1$ بود، راس‌های مسیر را به ترتیب و با فاصله از هم چاپ کنید. خروجی شما باید جایگشتی از اعداد $1$ تا $n$ باشد و خود ریشه را شامل نمی‌شود. دقت کنید که اگر $T = 0$ بود، شما نباید هیچ خروجی دیگری بدهید! # محدودیت‌ها $$1 \leq Q \leq 300 \, 000$$ $$1 \leq n \leq 300 \, 000$$ $$T \in \{ 0, 1 \}$$ $$0 \leq p_i < i$$ $$1 \leq a_i \leq 10^9$$ + جمع مقادیر $n$ به ازای تمام سناریوها از $300 \, 000$ بیشتر نمی‌شود. # زیرمسئله‌ها | زیرمسئله | نمره | محدودیت |:------------------:|:----------:|:------------------:| | ۱ | ۱۲ | $T = 0$ و $p_i = 0$ به ازای تمامی $i$ ها برقرار است. | | ۲ | ۱۵ | $T = 1$ و $p_i = 0$ به ازای تمامی $i$ ها برقرار است. | | ۳ | ۴۱ | $T = 0$ | | ۴ | ۳۲ | $T = 1$ | # مثال ## ورودی نمونه ۱ ``` 4 1 0 0 0 4 1 0 2 0 3 0 1 0 4 4 1 0 0 1 0 2 0 2 0 4 1 0 0 1 0 2 1 2 0 ``` ## خروجی نمونه ۱ ``` Yes Yes 1 3 2 4 No Yes 1 2 4 3 ```

حل سؤال در بانک سؤالات