Find a shortest path from s to t by BFS, enqueueing smaller neighbors first.

Input

The first line contains n, m, s, and t. The next m lines contain undirected edges.

• 1 <= s, t <= n <= 1000

Output

Print the selected shortest path, or -1 if t is unreachable.

Example

Input

6 6 1 6
1 3
1 2
2 4
3 4
4 5
5 6

Output

1 2 4 5 6