- محدودیت زمان: ۵ ثانیه
- محدودیت حافظه: ۵۱۲ مگابایت
- روز ۳ دوره ۳۰
اکبر یک بازی Crawler Dungeon جدید به اسم Keys! خریده است. او آن قدر معتاد این بازی شده است که چندین ساعت به طور متوالی آن را بازی کرده است.
هر Dungeon این بازی به این صورت است که از تعداد $n$ اتاق و $n-1$ در تشکیل شده است. با توجه به این که این اتاق‌ها باید همبند باشند، گراف ارتباط بین این اتاق‌ها باید به صورت درخت باشد. توجه کنید که منظور از گراف ارتباط‌ها گرافی است که رئوس آن متناظر با اتاق‌ها و هر یال آن معادل در بین دو اتاق است.
بازی از اتاق $s$ شروع می‌شود، و اکبر باید به اتاق $t$ برود که ورودی Dungeon بعدی است.
اما $m$ تا از این در‌ها قفل هستند که کلید‌های آن‌ها می‌توانند در اتاق‌های دیگری باشند. شخصیت اکبر در بازی تنها توانایی حمل یک کلید را دارد و اگر کلیدی را برداشت، تا زمانی که در متناظر با آن کلید را باز نکند نمی‌تواند آن کلید را زمین بگذارد.
همچنین 1 ثانیه طول می‌کشد که شخصیت اکبر از یک اتاق به اتاق مجاورش برود. توجه کنید که اگر یک در را با کلید باز کنیم، شخصیت اکبر به اتاق بعدی نمی‌رود و در همان اتاق باقی می‌ماند؛ این فرایند، زمان نمی‌برد و بلافاصله انجام می‌شود. رکورد اکبر در این بازی در واقع مدت زمانی است که طول می‌کشد از $s$ به $t$ برود.
اکبر که خیلی این بازی را دوست دارد، دلش می‌خواهد که رکورد جهانی این بازی را بزند! برای همین از شما خواسته برنامه‌ای بنویسید که با ورودی گرفتن درخت مربوط به Dungeon و اطلاعات کلید‌ها، کمینه زمان مورد نیاز برای رفتن به Dungeon بعدی را خروجی بدهد.
ورودی
در خط اول $n$ آمده است، که تعداد اتاق‌های Dungeon اکبر را مشخص می‌کند.
در خط بعدی اعداد $s$ و $t$ آمده‌اند، که به ترتیب مربوط به اتاق شروع Dungeon و اتاق ورودی Dungeon بعدی است.
در $n-1$ خط بعدی، اطلاعات مربوط به در‌ها و کلید‌ها به صورت $u:v:w$ آمده است که به این معنی است یک در بین اتاق $u$ و $v$ وجود دارد. همچنین اگر $w=0$ باشد، به این معنی است که این در قفل نیست و در غیر این صورت به این معنی است که این در قفل است و کلید آن در اتاق $w$ قرار دارد.
$$1 \leq n \leq 10^6$$ $$1 \le s,t,u,v \le n$$ $$0 \le w \le n$$ $$0 \leq m \leq 20$$
خروجی
در تنها خط خروجی، کمینه زمان مورد نیاز اکبر برای این که از $s$ به $t$ برود را چاپ کنید.
زیرمسئله‌ها
| زیرمسئله | نمره | محدودیت |
|---|---|---|
| ۱ | ۲۳ | $n \le 100\ 000,\ m \le 8$ |
| ۲ | ۳۶ | $n \le 7000$ |
| ۳ | ۴۱ | بدون محدودیت اضافی |
مثال
ورودی نمونه ۱
4
1 4
1 2 0
1 3 2
3 4 1
خروجی نمونه ۱
4
ورودی نمونه ۲
5
3 1
1 2 5
2 3 4
3 4 0
4 5 2
خروجی نمونه ۲
10
ارسال پاسخ برای این سؤال