Yo`nalishlar
Hozirda online

Statistika

Masalalar soni: 909

Foydalanuvchilar soni: 8824

Jo'natishlar soni: 714623

Muhokama yozuvlari: 4541

Yangiliklar soni: 98

Yangiliklar izohlari: 1177


So'ngi izohlar

748. The shortest path
Vaqt limiti: 1 sekund
Xotira limiti: 64 MB

Undiriented graph is given. Find the shortest path from vertex a to vertex b.

Input

The first line contains two integers n and m (1  n  100000, 0  m  100000) - the number of vertices and edges. The second line contains two integers a and b - the starting and ending point correspondingly. The next m lines describe the edges.

Output

    If the path between a and b does not exist, print -1. Otherwise print in the first line  the length l of the shortest path between these two vertices in number of edges.

Samples

Input

Output

1

4 5

1 4

1 3

3 2

2 4

2 1

2 3

2

2

4 4

2 3

2 1

2 4

4 3

1 3

2

 

Tayyorladi: Azat Yusupov
Text from: e-olimp.com
Mening urinishlarim(0) Muhokama (4) Jo'natish Eng yaxshi yechimlar Barcha muvaffaqiyatli urinishlar(55) Barcha urinishlar(184)