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

هر وقت که آن‌ها حکومتی را شکست می‌دادند، همه شهرهارا جز بزرگ‌ترین شهر ویران می‌کردند، بزرگترین شهر را به قلمرو خود می‌افزودند و یک جاده از بزرگ‌ترین شهر به یکی از شهرهای خود می‌کشیدند که بتوانند بین همه شهرهای قلمرو خود سفر کنند. همچنین، اگر شهر تسخیرشده به اندازه کافی بزرگ بود، آن‌را پایتخت خود می‌کردند.

نفوذپذیری یکی از شهرهای مایو به صورت تعداد جاده‌های لازم برای رسیدن به پایتخت تعریف می‌شود.

ما لیست همه‌ی حکومت‌هایی که مایو شکست داده‌‌است و جاده‌هایی که ساخته‌است را داریم. می‌خواهیم بیش‌ترین میزان نفو‌ذپذیری یک‌ شهر را بعد از اضافه‌شدن هر شهر به مایو محاسبه کنیم. برای ساده‌شدن خروجی، $v_2 + v_3 + \cdots + v_n$ را چاپ کنید که $v_i$،‌ بیش‌ترین نفوذپذیری یک‌شهر پس از اضافه شدن شهر $i$ام است.

• تست‌های مختلفی در ورودی وجود دارد. در خط اول هر تست عدد$n$($1 \leq n \leq 100000$)، تعداد شهرهای مایو داده می‌شود. شهرها به‌ترتیب اضافه‌شدن به امپراتوری از ۱ تا $n$ شماره‌گذاری شده‌اند. یعنی اول کار تنها شهر ۱ وجود دارد و پایتخت است.
• سپس در هر یک از $n-1$ خط بعد دو عدد $j$ و $c$ آمده‌اند که یعنی شهر $i+1$ از طریق جاده به شهر $j$ وصل شده‌است و $c$ اگر ناصفر باشد یعنی این شهر از این پس پایتخت خواهد شد و درغیر این‌صورت صفر خواهد بود.
• در آخرین خط ورودی عدد ۰ آمده‌است.

به ازای هر تست، در یک خط، جمع بیش‌ترین نفوذپذیری را (همان‌طور که در صورت سوال ذکر شده‌است) چاپ کنید.

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

• سوال قبل