+ محدودیت زمان: ۱ ثانیه + محدودیت حافظه: ۵۱۲ مگابایت ---------- تیزی و کسری روی یک گراف همبند بازی میکنند. هر کدام از آنها روی یکی از راس های گراف قرار گرفته‌اند. دو راس از این گراف راس های سرور نام دارند که این دو راس حتما با یک یال بهم وصلند. تیزی و کسری یکی درمیان حرکت میکنند و ابتدا تیزی حرکت میکند. آنها در هر ثانیه میتوانند به یکی از راس های مجاور راس فعلی خود بروند اما مجبور به حرکت نیستند. قطع کردن سیم های یک سرور هم یک ثانیه طول میکشد. هدف تیزی این است که به یک راس سرور برسد و سیم آن را قطع کند. کسری میخواهد جلوی او را بگیرد. کسری در صورتی برنده میشود که تا ابد جلوی کشیدن سیم سرور توسط تیزی را بگیرد. یا اینکه قبل از کشیده شدن سیم سرور با تیزی در یک راس باشد. اما کسری خوابش می‌آید و میخواهد بیشتر بخوابد. او میخواهد آنقدر بخوابد تا بعد از بیدار شدن همچنان مطمئن باشد میتواند از تیزی ببرد. بیشترین تعداد ثانیه‌ای که کسری میتواند به جای بازی کردن بخوابد را پیدا کنید. دقت کنید که کسری در زمانی که خواب است حتی اگر با تیزی در یک راس قرار بگیرد برنده نمیشود. # ورودی در خط اول ورودی $n$ و $m$ به شما داده میشود که به ترتیب تعداد راس های گراف و تعداد یال های آن است. در خط بعدی ۴ عدد $k$ و $t$ و $a$ و $b$ به شما داده میشود که $t$ شماره راس ابتدایی تیزی است و $k$ شماره راس ابتدایی کسری. $a$ و $b$ شماره راس های دو سرور هستند. در هر یک از $m$ خط بعدی دو عدد $v$ و $u$ به شما داده میشود که نشان دهنده ی یک یال بین $v$ و $u$ است. $$4 \leq n \leq 200\ 000$$ $$3 \leq m \leq 600\ 000$$ $$1\leq t,k,a,b,v,u \leq n$$ # خروجی در تنها خط خروجی حداکثر زمانی که کسری میتواند بخوابد تا باز هم تیزی را ببرد بدهید. اگر کسری نمیتواند تیزی را ببرد $-1$ چاپ کنید. # زیر مسئله‌ها | زیرمسئله | نمره | محدودیت | |:---------------------:|:----------------:|:-------------------:| | ۱ | ۳۰ | $$n \le 800, m\le 1 \ 600$$| | ۲ | ۷۰ | بدون محدودیت اضافی| # مثال ## ورودی نمونه ۱ ``` 6 6 1 2 3 4 1 5 5 6 6 3 6 4 1 2 3 4 ``` ## خروجی نمونه ۱ ``` 1 ``` ## ورودی نمونه ۲ ``` 6 7 5 6 1 2 6 3 1 2 1 3 2 3 1 5 2 4 5 4 ``` ## خروجی نمونه ۲ ``` 0 ```

حل سؤال در بانک سؤالات