====== اجداد پدری ======
درخت ‎$T$‎ به ریشه‌ی ‎$r$‎ داده شده است. پدر رأس ‎$v$‎ را در این درخت با ‎$P(v)$‎ 
نمایش می‌دهیم و ‎$P(r)$‎ را برابر خود ‎$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$‎ را بنویسید. 



===== محدودیت‌ها =====


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

===== ورودي و خروجي نمونه =====

<WRAP :en>
^  ورودي نمونه  ^  خروجي نمونه  ^
|5 3 1 \\ 1 2 \\ 2 3 \\ 3 4 \\ 4 5|‎5 \\ 3 \\ 3 \\ 3 \\ 7|

</WRAP>
  * [[سوال ۸|سوال بعد]]
  * [[سوال ۶|سوال قبل]]