The shortest path#4853

The shortest path

2 seconds
128 megabytes
Easy

An undirected graph is given. Find the shortest path from vertex to vertex .

Input

The first line contains two integers and m~(1 \le n \le 5 \cdot 10^4, 1 \le m \le 10^5) — the number of vertices and edges, respectively.

The second line contains two integers and — the starting and ending vertices.

Each of the following lines describe an edge.

Output

If there is no path from to , print .

Otherwise, print the length of the shortest path on the first line, and on the second line print l + 1 numbers: the sequence of vertices along this path.

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading