درخت $T$ به ریشه‌ی $r$ داده شده است. پدر رأس $v$ را در این درخت با $P(v)$ نمایش می‌دهیم و $P®$ را برابر خود $r$ در نظر می‌گیریم. حال پدر $i$اُمِ رأس $v$ (با نشان $P^i(v)$) به این صورت تعریف می‌شود که $P^0(v)=v$ و برای $i>0$ داریم $P^i(v)=P(P^{i-1}(v))$.

اکنون از شما خواسته‌شده تا برای هر رأسِ $v$ جمع اندیس‌های پدر $k$اُمِ $v$ و پدران بالاترش (تا ریشه) را حساب کنید. دقّت کنید که اگر رأس $u$، هم‌زمان نقش چندین پدر را برای رأس $v$ بازی کند، حداکثر یک‌ بار شمارده می‌شود.

• در سطر اوّل ورودی $n$، $r$ و $k$ آمده‌اند.
• در $n-1$ سطر بعد در هر سطر دو سر یک یال درخت آمده است.
• می‌توانید فرض کنید که رئوس درخت در بازه‌ی $[1..n]$ قرار دارند.
• $1\leq k,n\leq 500000$

در سطر $i$اُم، عدد مربوط به رأس $i$ را بنویسید.

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