Find the path from s to t produced by DFS when smaller neighbors are explored 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 DFS path from s to t, 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