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

در یک مدرسه $n$ دوست دور هم جمع شده‌اند. این دوست‌ها را می‌توانیم با اعداد $1$ تا $n$ شماره‌گذاری کنیم.

تعدادی رابطه «دهن‌لقی» بین این دوستان وجود دارد؛ یعنی اگر این رابطه از $u$ به $v$ وجود داشته باشد. اگر $u$ رازی از کسی را بداند در یک شب با $v$ در یک کافه قرار می‌گذارد و آن راز را به $v$ می‌گوید. توجه کنید رابطه‌ی «دهن‌لقی» لزوماً دو طرفه نیست.

حال در یک روز، $s$ یک راز برای $t$ از زندگی شخصی‌اش می‌گوید. همچنین می‌دانیم که $t$ رابطه دهن‌لقی با $s$ ندارد.

توجه کنید انتقال یک راز از یک‌نفر به یک نفر دیگر یک روز طول می‌کشد. چون یک روز در قراری باید آن را بشنود و در یک روز دیگر این راز را منتقل کند.

قرارها نیز دو نفره هستند و به صورت گروهی برگزار نمی‌شود.

حداقل چند روز طول می‌کشد تا این راز مجدداً به $s$، توسط دوستی دیگر گفته شود و او متوجه فاش شدن رازش شود.

ورودی

ورودی شامل $T$ تست نمونه است. $$1 \leq T \leq 100 , 000$$

برای هر تست، در سطر اول ورودی چهار عدد صحیح و مثبت $n$، $m$، $s$ و $t$ آمده است که به ترتیب نشان‌دهنده‌ی تعداد دانش‌آموزان، تعداد رابطه‌های دهن‌لقی و شخص $s$ و $t$ است.

$$2 \leq n \leq 100 , 000$$ $$0 \leq m \leq \min{n(n - 1), 100 , 000}$$ $$1 \leq s \neq t \leq n$$

تضمین می‌شود $t$ رابطه دهن‌لقی با $s$ ندارد. در $m$ خط بعدی دو عدد صحیح $u$ و $v$ که با یک فاصله از هم جدا شده‌اند آمده است و نشان‌دهنده‌ی وجود رابطه دهن‌لقی از $u$ به $v$ است.

$$1 \leq u \neq v \leq n$$

تضمین می‌شود هر رابطه حداکثر یکبار ورودی داده شود همچنین $\sum n + m$ به‌ازای همه $T$ تست از ۱۰۰‌،۰۰۰ بیشتر نمی‌شود.

خروجی

در تنها سطر خروجی یک عدد صحیح و مثبت چاپ کنید که حداقل تعداد روزی که باید بگذرد تا $s$ متوجه فاش شدن رازش شود.

اگر هیچ‌وقت چنین اتفاقی نمی‌افتد -1 چاپ کنید.

مثال

ورودی نمونه ۱

2
3 3 1 2
1 2
2 3
3 1
4 3 2 3
1 3
3 4
4 1

خروجی نمونه ۱

2
-1

تست اول.

• در روز اول ۱ رازش را به ۲ می‌گوید.
• در روز دوم ۲ راز ۱ را به ۳ می‌گوید.
• در روز سوم ۳ راز ۱ را به ۱ می‌گوید.

پس در روز سوم (بعد از گذشت ۲ روز)، شخص ۱ متوجه فاش شدن رازش می‌شود. بنابراین پاسخ این تست برابر ۲ است.

تست دوم.

• در روز اول ۲ رازش را به ۳ می‌گوید.
• در روز دوم ۳ راز ۲ را به ۴ می‌گوید.
• در روز سوم ۴ راز ۲ را به ۱ می‌گوید.

در روز چهارم همه راز ۲ را می‌دانند اما هیچ‌وقت ۲ متوجه نمی‌شود که رازش فاش شده است. بنابراین پاسخ مسئله ۱- خواهد بود.