Гобомобіль

Обмеження: 2 сек., 256 МіБ

Створивши своє королівство, Хобот Четвертий установив дуже цікаві правила дорожнього руху. По кожній дорозі дозволений односторонній рух, причому кожного наступного дня напрям руху змінюється на протилежний.

Один юний Гобіт нещодавно сконструював унікальний у всьому королівстві гобомобіль. Унікальність машини полягає в тому, що почавши рух, вона не може зупинитись (хіба один раз і назавжди). За один день чудо-машина проїжджає рівно одну дорогу.

Дороги побудовані таким способом, що всі вони рівні за довжиною, ніде не перетинаються, за винятком міст, які вони сполучають. Також між парою міст може бути декілька доріг та можливе існування дороги, що веде від деякого міста до нього ж.

Вам необхідно визначити мінімальну кількість днів, за яку юний Гобіт зможе добратися на своєму гобомобілі з міста $a$ до міста $b$.

Вхідні дані

У першому рядку містяться чотири цілих числа $n$, $m$, $a$, $b$ — кількість міст, кількість доріг, початкове й кінцеве місто.

Наступні $m$ рядків містять по два цілих числа $u_i$, $v_i$ — номери міст, які сполучає дорога $i$. Причому першого дня рух дозволено з міста $u_i$ в $v_i$, другого дня — навпаки і т. д.

Вихідні дані

У першому рядку виведіть ціле число — мінімальну кількість днів, через яку Гобіт зможе добратися в місто $b$, не порушуючи правил дорожнього руху. Якщо Гобіт за таких умов не зможе досягнути мети взагалі — виведіть -1.

У другому рядку виведіть аналогічну інформацію для випадку, коли Гобіт може порушувати правила дорожнього руху королівства. Уявіть собі: навіть Гобіти вміють давати хабарі.

Обмеження

$1 \le n, m \le 10^5$,

$1 \le a, b, u_i, v_i \le n$.

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
7 5 4 7 1 2 3 2 3 1 1 4 7 1	6 2

Примітки

Зауважте, що Гобіт необов’язково має заводити свій транспорт першого дня.