قله‌ی ترافیک روی درخت


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

اگر به رفتار استف‌های کدکاپ ۳ در طول مسابقه دقت کرده‌باشید، درمی‌یابید که همه استفا عاشق مصطفی هستند.

کشور کوئرا از nn شهر تشکیل شده است که این nn شهر با n1n - 1 جاده دوطرفه به هم متصل شده‌اند به طوری که از هر شهر می‌توان با طی کردن تعدادی جاده به شهر شماره ۱ رسید.

شهر شماره ۱ پایتخت کشور کوئراست و هرساله مجموعه مسابقات کدکاپ در این شهر برگزار می‌شود.

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

متاسفانه مسابقه کدکاپ با تعمیر جاده‌های کشور کوئرا توسط وزارت راه و ترابری، مصادف شده است و جاده‌ی شماره ii که دو شهر xix_i و yiy_i را به هم وصل می‌کند از روز lil_i تا روز rir_i در درست تعمیر است و امکان عبور از آن وجود ندارد. (یعنی اگر در روز kk‌ ام به شهر xix_i برسیم به طوری که likri l_i \le k \le r_i، باید تا روز ri+1r_i + 1 صبر کنیم تا بتوانیم به شهر yiy_i برویم)

به دلیل پیشرفت فناوری‌های ترابری در کشور کوئرا مدت زمانی که طول می‌کشد تا از یک جاده عبور کنیم (به شرط باز بودن آن) به صفر ثانیه رسیده‌است. یعنی در طول سفر از یک شهر به شهر دیگر تنها چیزی‌ که باعث معطل شدن ما می‌شود بسته بودن جاده‌‌ها است.

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

دقت کنید که تمامی استف‌ها در ثانیه‌ صفر از مبدا خود به سمت شهر ۱ راه می‌افتند.

ورودی🔗

در یک خط عدد nn که تعداد شهرهای کشور کوئراست به شما داده می‌شود.

در n1n - 1 خط بعدی، درهر خط ۴ عدد xix_i و yiy_i و lil_i و rir_i به شما داده می‌شود که به این معناست که جاده ii ام شهر xix_i و yiy_i را به هم وصل می‌کند و در زمان lil_i تا rir_i در دست تعمیر است.

2n500 000 2 \le n \le 500 \ 000 1xi,yin 1 \le x_i , y_i \le n 0liri500 000 0 \le l_i \le r_i \le 500 \ 000

تضمین می‌شود که با جاده‌های داده شده، از همه‌ی شهرها می‌توان به شهر شماره ۱ رسید.

خروجی🔗

در nn خط به ازای هر شهر یک عدد چاپ کنید که نشان می‌دهد استف‌های آن شهر در روز چندم به شهر ۱ ام می‌رسند.

مثال🔗

ورودی نمونه ۱🔗

2
1 2 1 2
Plain text

خروجی نمونه ۱🔗

0
0
Plain text

ورودی نمونه ۲🔗

3
1 2 3 4
2 3 0 2
Plain text

خروجی نمونه ۲🔗

0
0
5
Plain text